// =INDEX(A$1:A$200,(ROW()-1)*4+1)

import java.util.*;

class CodingInterviewSolution {
    // 面试题 01.01. 判定字符是否唯一
    // 实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
    // 限制：
    // 0 <= len(s) <= 100
    // s[i]仅包含小写字母
    // 如果你不使用额外的数据结构，会很加分。

    // 方法一：（自己写的）位运算-时间复杂度：O(n)，空间复杂度：O(1)
    public boolean isUnique(String astr) {
        if (astr.length() > 26)
            return false;
        int count = 0;
        for (char c : astr.toCharArray()) {
            int bit = 1 << (c - 'a');
            if ((count & bit) != 0)
                return false;
            else
                count = count | bit;
        }
        return true;
    }

    // 面试题 01.02. 判定是否互为字符重排
    // 给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
    // 说明：
    // 0 <= len(s1) <= 100
    // 0 <= len(s2) <= 100

    // 方法一：排序，时间复杂度：O(nlogn)，空间复杂度：O(logn)
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length())
            return false;

        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }

    // 方法二：（自己写的）哈希表，时间复杂度：O(n)，空间复杂度：O(S)
    // 由于字符串只包含 128 种不同的字符，因此也可以维护一个长度为 128 的频次数组
    public boolean CheckPermutation2(String s1, String s2) {
        if (s1.length() != s2.length())
            return false;
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s1.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);

        for (char c : s2.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) - 1);
            if (map.get(c) < 0)
                return false;
        }
        return true;
    }

    // 面试题 01.03. URL化
    // URL化。编写一种方法，将字符串中的空格全部替换为%20。
    // 假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。
    // （注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）

    // 方法一：（自己写的）遍历 + 拼接-时间复杂度：O(n)，空间复杂度：O(1)
    public String replaceSpaces(String S, int length) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++) {
            char c = S.charAt(i);
            if (c == ' ')
                sb.append("%20");
            else
                sb.append(c);
        }
        return sb.toString();
    }

    // 面试题 01.04. 回文排列
    // 给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
    // 回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
    // 回文串不一定是字典当中的单词。

    // 方法一：（自己写的）哈希表-时间复杂度：O(n)，空间复杂度：O(1)
    // 由于不知道包含哪些字符，保险起见。若全为小写字母还可以使用位运算 出现1,2,3次 对应位 1,0,1
    public boolean canPermutePalindrome11(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);

        boolean valid = true;
        for (int value : map.values())
            if ((value & 1) == 1) {
                if (!valid)
                    return false;
                valid = false;
            }

        return true;
    }

    // 面试题 01.05. 一次编辑
    // 字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。
    // 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

    // 方法一：双指针+ 分情况讨论-时间复杂度：O(n)，空间复杂度：O(1)
    public boolean oneEditAway(String first, String second) {
        int m = first.length(), n = second.length();
        if (n - m == 1)
            return oneInsert(first, second);
        else if (m - n == 1)
            return oneInsert(second, first);
        else if (m == n) {
            boolean foundDifference = false;
            for (int i = 0; i < m; i++)
                if (first.charAt(i) != second.charAt(i)) {
                    if (!foundDifference)
                        foundDifference = true;
                    else
                        return false;
                }
            return true;
        } else
            return false;
    }

    public boolean oneInsert(String shorter, String longer) {
        int length1 = shorter.length(), length2 = longer.length();
        int index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            if (shorter.charAt(index1) == longer.charAt(index2))
                index1++;
            index2++;
            if (index2 - index1 > 1)
                return false;
        }
        return true;
    }

    // 方法一：（自己写的）双指针 + 分情况讨论-时间复杂度：O(n)，空间复杂度：O(1)
    public boolean oneEditAway11(String first, String second) {
        if (Math.abs(first.length() - second.length()) > 1)
            return false;
        int index1 = 0, index2 = 0;
        boolean canModify = true;
        while (index1 < first.length() && index2 < second.length()) {
            if (first.charAt(index1) == second.charAt(index2)) {
                index1++;
                index2++;
                continue;
            }

            if (!canModify)
                return false;
            canModify = false;
            if (first.length() > second.length())
                index1++;
            else if (first.length() < second.length())
                index2++;
            else {
                index1++;
                index2++;
            }
        }
        return true;
    }

    // 面试题 01.06. 字符串压缩
    // 字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。
    // 比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。
    // 你可以假设字符串中只包含大小写英文字母（a至z）。

    // 方法一：模拟-时间复杂度：O(n)，空间复杂度：O(1)
    public String compressString(String S) {
        if (S.length() == 0) // 空串处理
            return S;

        StringBuffer ans = new StringBuffer();
        int cnt = 1;
        char ch = S.charAt(0);
        for (int i = 1; i < S.length(); ++i) {
            if (ch == S.charAt(i))
                cnt++;
            else {
                ans.append(ch);
                ans.append(cnt);
                ch = S.charAt(i);
                cnt = 1;
            }
        }
        ans.append(ch);
        ans.append(cnt);
        return ans.length() >= S.length() ? S : ans.toString();
    }

    // 方法一：（自己写的）模拟-时间复杂度：O(n)，空间复杂度：O(1)
    public String compressString11(String S) {
        if (S.equals(""))
            return "";
        StringBuilder sb = new StringBuilder();
        int index = 1, count = 1;
        while (index < S.length()) {
            if (S.charAt(index) == S.charAt(index - 1))
                count++;
            else {
                sb.append(S.charAt(index - 1));
                sb.append(count);
                count = 1;
            }
            index++;
        }
        sb.append(S.charAt(index - 1));
        sb.append(count);

        if (sb.length() >= S.length())
            return S;
        else
            return sb.toString();
    }

    // 面试题 01.07. 旋转矩阵（主站48.）
    // 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
    // 不占用额外内存空间能否做到？

    // 方法一：用翻转代替旋转-时间复杂度：O(n^2)，空间复杂度：O(1)
    // 先将其通过水平轴翻转，再根据主对角线翻转，得到答案
    // 也可以：先主对角线翻转，则后垂直翻转
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 水平翻转
        for (int i = 0; i < n / 2; ++i)
            for (int j = 0; j < n; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }

        // 主对角线翻转
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < i; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
    }

    // 方法一：（自己写的）用翻转代替旋转-时间复杂度：O(n^2)，空间复杂度：O(1)
    public void rotate11(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }

    // 方法二：原地旋转-时间复杂度：O(n^2)，空间复杂度：O(1)
    // 四数交换为一组
    public void rotate2(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; ++i)
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }

    }

    // 方法二：（自己写的）原地旋转-时间复杂度：O(n^2)，空间复杂度：O(1)
    public void rotate22(int[][] matrix) {
        int n = matrix.length;
        for (int range = n; range > 1; range -= 2) {
            int upRow = n / 2 - range / 2;
            int downRow = n - 1 - upRow;
            int leftColumn = upRow;
            int rightColumn = downRow;
            for (int i = leftColumn; i < rightColumn; i++) {
                int iInverse = n - 1 - i;
                int temp = matrix[upRow][i];
                matrix[upRow][i] = matrix[iInverse][leftColumn];
                matrix[iInverse][leftColumn] = matrix[downRow][iInverse];
                matrix[downRow][iInverse] = matrix[i][rightColumn];
                matrix[i][rightColumn] = temp;
            }
        }
    }

    // 面试题 01.08. 零矩阵
    // 编写一种算法，若 M × N 矩阵中某个元素为0，则将其所在的行与列清零。
    // 进阶：能否不使用额外空间？

    // 方法一：使用标记数组-时间复杂度：O(mn)，空间复杂度：O(m+n)
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (matrix[i][j] == 0)
                    row[i] = col[j] = true;

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (row[i] || col[j])
                    matrix[i][j] = 0;
    }

    // 方法一：（自己写的）使用标记数组-时间复杂度：O(mn)，空间复杂度：O(m+n)
    public void setZeroes11(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        Set<Integer> rows = new HashSet<>();
        Set<Integer> columns = new HashSet<>();

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != 0)
                    continue;
                rows.add(i);
                columns.add(j);
            }

        for (int row : rows)
            for (int j = 0; j < n; j++)
                matrix[row][j] = 0;

        for (int column : columns)
            for (int i = 0; i < m; i++)
                matrix[i][column] = 0;
    }

    // 方法二：使用两个标记变量-时间复杂度：O(mn)，空间复杂度：O(1)
    // 我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1) 的额外空间。
    // 但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 0。
    // 因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。
    public void setZeroes2(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false, flagRow0 = false;
        for (int i = 0; i < m; i++)
            if (matrix[i][0] == 0)
                flagCol0 = true;

        for (int j = 0; j < n; j++)
            if (matrix[0][j] == 0)
                flagRow0 = true;

        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (matrix[i][j] == 0)
                    matrix[i][0] = matrix[0][j] = 0;

        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;

        if (flagCol0)
            for (int i = 0; i < m; i++)
                matrix[i][0] = 0;

        if (flagRow0)
            for (int j = 0; j < n; j++)
                matrix[0][j] = 0;
    }

    // 方法三：使用一个标记变量-时间复杂度：O(mn)，空间复杂度：O(1)
    // 我们可以对方法二进一步优化，只使用一个标记变量记录第一列是否原本存在 0。
    // 这样，第一列的第一个元素即可以标记第一行是否出现 0。
    // 但为了防止每一列的第一个元素被提前更新，我们需要从最后一行开始，倒序地处理矩阵元素。
    public void setZeroes3(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0)
                flagCol0 = true;

            for (int j = 1; j < n; j++)
                if (matrix[i][j] == 0)
                    matrix[i][0] = matrix[0][j] = 0;
        }
         
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++)
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;

            if (flagCol0)
                matrix[i][0] = 0;
        }
    }

    // 面试题 01.09. 字符串轮转
    // 字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。
    // 提示：
    // 字符串长度在[0, 100000]范围内。
    // 说明:
    // 你能只调用一次检查子串的方法吗？

    // 方法一：搜索子字符串-时间复杂度：O(n)，空间复杂度：O(n)
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length())
            return false;
        s2 = s2 + s2;
        if (s2.contains(s1))
            return true;
        else
            return false;
    }

    // 面试题 02.01. 移除重复节点
    // 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
    // 提示：
    // 链表长度在[0, 20000]范围内。
    // 链表元素在[0, 20000]范围内。
    // 进阶：
    // 如果不得使用临时缓冲区，该怎么解决？

    // 方法一：哈希表-时间复杂度：O(n)，空间复杂度：O(n)
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null)
            return head;

        Set<Integer> occurred = new HashSet<Integer>();
        occurred.add(head.val);
        ListNode pos = head;
        // 枚举前驱节点
        while (pos.next != null) {
            // 当前待删除节点
            ListNode cur = pos.next;
            if (occurred.add(cur.val))
                pos = pos.next;
            else
                pos.next = pos.next.next;
        }
        pos.next = null;
        return head;
    }

    // 方法一：（自己写的）哈希表-时间复杂度：O(n)，空间复杂度：O(n)
    public ListNode removeDuplicateNodes11(ListNode head) {
        Set<Integer> set = new HashSet<>();
        ListNode dummyHead = new ListNode(-1, head);
        ListNode prev = dummyHead;
        ListNode curr = head;
        while (curr != null) {
            if (set.contains(curr.val)) {
                prev.next = curr.next;
                curr = curr.next;
            } else {
                set.add(curr.val);
                prev = prev.next;
                curr = curr.next;
            }
        }
        return dummyHead.next;
    }

    // 方法一：（自己写的）哈希表-时间复杂度：O(n)，空间复杂度：O(n)
    // 使用 LinkedHashSet 重构链，没有原地修改
    public ListNode removeDuplicateNodes111(ListNode head) {
        LinkedHashSet<Integer> set = new LinkedHashSet<>();
        while (head != null) {
            set.add(head.val);
            head = head.next;
        }
        ListNode dummyHead = new ListNode(-1);
        ListNode curr = dummyHead;
        for (int val : set) {
            curr.next = new ListNode(val);
            curr = curr.next;
        }
        return dummyHead.next;
    }

    // 方法二：两重循环-时间复杂度：O(n2)，空间复杂度：O(1)
    // 在保证方法一时间复杂度 O(N) 的前提下，是不存在这样的方法的。
    // 因此我们需要增加时间复杂度，使得我们可以仅使用常数的空间来完成本题。
    // 一种简单的方法是：
    // 我们在给定的链表上使用两重循环，其中第一重循环从链表的头节点开始，枚举一个保留的节点，这是因为我们保留的是「最开始出现的节点」。
    // 第二重循环从枚举的保留节点开始，到链表的末尾结束，将所有与保留节点相同的节点全部移除。
    public ListNode removeDuplicateNodes2(ListNode head) {
        ListNode ob = head;
        while (ob != null) {
            ListNode oc = ob;
            while (oc.next != null) {
                if (oc.next.val == ob.val)
                    oc.next = oc.next.next;
                else
                    oc = oc.next;
            }
            ob = ob.next;
        }
        return head;
    }

    // 方法二：（自己写的）两重循环-时间复杂度：O(n2)，空间复杂度：O(1)
    // 第一重循环从链表的头节点开始，枚举节点。
    // 第二重循环从头节点开始，到第一重循环枚举的节点结束，如果有相同值的节点，则删除枚举节点。
    public ListNode removeDuplicateNodes22(ListNode head) {
        ListNode dummyHead = new ListNode(-1, head);
        ListNode prev = dummyHead, curr = head;
        while (curr != null) {
            boolean isDuplicate = false;
            ListNode second = head;
            while (second != curr) {
                if (second.val == curr.val) {
                    isDuplicate = true;
                    break;
                }
                second = second.next;
            }

            if (isDuplicate) {
                prev.next = curr.next;
                curr = curr.next;
            } else {
                prev = prev.next;
                curr = curr.next;
            }
        }
        return dummyHead.next;
    }

    // 面试题 02.02. 返回倒数第 k 个节点
    // 实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
    // 说明：
    // 给定的 k 保证是有效的。

    // 方法一：（自己写的）双指针 快慢指针-时间复杂度：O(n)，空间复杂度：O(1)
    public int kthToLast(ListNode head, int k) {
        ListNode fast = head, slow = head;
        while (k != 0) {
            k--;
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

    // 面试题 02.03. 删除中间节点
    // 若链表中的某个节点，既不是链表头节点，也不是链表尾节点，则称其为该链表的「中间节点」。
    // 假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。
    // 例如，传入节点 c（位于单向链表 a->b->c->d->e->f 中），将其删除后，剩余链表为 a->b->d->e->f

    // 方法一：（自己写的）当前节点拷贝后继节点值，删除后继节点-时间复杂度：O(1)，空间复杂度：O(1)
    public void deleteNode(ListNode node) {
        if (node.next == null) {
            node = null;
            return;
        }
        ListNode next = node.next;
        node.val = next.val;
        node.next = next.next;
    }

    // 面试题 02.04. 分割链表
    // 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
    // 你不需要 保留 每个分区中各节点的初始相对位置。
    //  提示：
    // 链表中节点的数目在范围 [0, 200] 内
    // -100 <= Node.val <= 100
    // -200 <= x <= 200

    // 方法一：模拟（两个链表）
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode smallHead = small;
        ListNode large = new ListNode(0);
        ListNode largeHead = large;
        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }
        large.next = null;
        small.next = largeHead.next;
        return smallHead.next;
    }

    // 面试题 02.05. 链表求和
    // 给定两个用链表表示的整数，每个节点包含一个数位。
    // 这些数位是反向存放的，也就是个位排在链表首部。
    // 编写函数对这两个整数求和，并用链表形式返回结果。
    // 进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?

    // 方法一：模拟-时间复杂度：O(max(m,n))，空间复杂度：O(1)
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null)
                head = tail = new ListNode(sum % 10);
            else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
        }
        if (carry > 0)
            tail.next = new ListNode(carry);
        return head;
    }

    // 方法一：（自己写的）模拟-时间复杂度：O(max(m,n))，空间复杂度：O(1)
    public ListNode addTwoNumbers11(ListNode l1, ListNode l2) {
        int adder = 0;
        ListNode dummyHead = new ListNode(-1);
        ListNode curr = dummyHead;
        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val + adder;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            adder = sum / 10;
            l1 = l1.next;
            l2 = l2.next;
        }
        while (l1 != null) {
            int sum = l1.val + adder;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            adder = sum / 10;
            l1 = l1.next;
        }
        while (l2 != null) {
            int sum = l2.val + adder;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            adder = sum / 10;
            l2 = l2.next;
        }
        if (adder != 0)
            curr.next = new ListNode(adder);
        return dummyHead.next;
    }

    // 面试题 02.06. 回文链表
    // 编写一个函数，检查输入的链表是否是回文的。
    // 进阶：
    // 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

    // 方法一：将值复制到数组中后用双指针法-时间复杂度：O(n)，空间复杂度：O(n)

    // 方法二：递归-时间复杂度：O(n)，空间复杂度：O(n)

    // 方法三：快慢指针-时间复杂度：O(n)，空间复杂度：O(1)
    // 最后会还原链表
    public boolean isPalindrome(ListNode head) {
        if (head == null)
            return true;
        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        while (p2 != null) {
            if (p1.val != p2.val)
                return false;
            p1 = p1.next;
            p2 = p2.next;
        }

        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return true;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    // 方法三：（自己写的）快慢指针-时间复杂度：O(n)，空间复杂度：O(1)
    // 最后不会还原链表
    public boolean isPalindrome3(ListNode head) {
        ListNode dummyHead = new ListNode(-1, head);
        ListNode fast = dummyHead, slow = dummyHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode first = head;
        ListNode second = slow.next;
        slow.next = null;

        ListNode prev = null;
        while (second != null) {
            ListNode next = second.next;
            second.next = prev;
            prev = second;
            second = next;
        }
        second = prev;

        while (first != null && second != null) {
            if (first.val != second.val)
                return false;
            first = first.next;
            second = second.next;
        }
        return true;
    }

    // 面试题 02.07. 链表相交
    // 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
    // 图示两个链表在节点 c1 开始相交：
    // 题目数据 保证 整个链式结构中不存在环。
    // 注意，函数返回结果后，链表必须 保持其原始结构 。
    // 提示：
    // listA 中节点数目为 m
    // listB 中节点数目为 n
    // 0 <= m, n <= 3 * 104
    // 1 <= Node.val <= 105
    // 0 <= skipA <= m
    // 0 <= skipB <= n
    // 如果 listA 和 listB 没有交点，intersectVal 为 0
    // 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
    // 进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

    // 方法一：哈希集合-时间复杂度：O(m+n)，空间复杂度：O(m)

    // 方法二：双指针-时间复杂度：O(m+n)，空间复杂度：O(1)
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null)
            return null;

        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    // 方法二：（自己写的）双指针-时间复杂度：O(m+n)，空间复杂度：O(1)
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode la = headA, lb = headB;
        while (la != lb) {
            if (la == null)
                la = headB;
            else
                la = la.next;

            if (lb == null)
                lb = headA;
            else
                lb = lb.next;
        }
        return la;
    }

    // 面试题 02.08. 环路检测
    // 给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。
    // 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
    // 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
    // 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
    // 进阶：
    // 你是否可以不用额外空间解决此题？

    // 方法一：哈希表-时间复杂度：O(n)，空间复杂度：O(n)

    // 方法二：快慢指针-时间复杂度：O(n)，空间复杂度：O(1)
    public ListNode detectCycle(ListNode head) {
        if (head == null)
            return null;

        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null)
                fast = fast.next.next;
            else
                return null;

            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }

    // 方法二：（自己写的）快慢指针-时间复杂度：O(n)，空间复杂度：O(1)
    public ListNode detectCycle2(ListNode head) {
        if (head == null || head.next == null)
            return null;
        ListNode fast = head.next.next, slow = head.next;
        while (fast != slow) {
            if (fast == null || fast.next == null)
                return null;
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    // 面试题 03.01. 三合一
    // 三合一。描述如何只用一个数组来实现三个栈。
    // 你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。
    // stackNum表示栈下标，value表示压入的值。
    // 构造函数会传入一个stackSize参数，代表每个栈的大小。
    // 提示：
    // 0 <= stackNum <= 2

    // 方法一：二维数组

    // 方法二：（自己写的）一维数组
    class TripleInOne {
        int stackSize;
        int[] stk;
        int sizes[] = new int[3];

        public TripleInOne(int stackSize) {
            this.stackSize = stackSize;
            stk = new int[stackSize * 3];
        }

        public void push(int stackNum, int value) {
            if (sizes[stackNum] == stackSize)
                return;
            int offset = stackSize * stackNum;
            stk[offset + sizes[stackNum]] = value;
            sizes[stackNum]++;
        }

        public int pop(int stackNum) {
            if (sizes[stackNum] == 0)
                return -1;
            int ans = peek(stackNum);
            sizes[stackNum]--;
            return ans;
        }

        public int peek(int stackNum) {
            if (sizes[stackNum] == 0)
                return -1;
            int offset = stackSize * stackNum;
            return stk[offset + sizes[stackNum] - 1];
        }

        public boolean isEmpty(int stackNum) {
            if (sizes[stackNum] == 0)
                return true;
            else
                return false;
        }
    }

    // 面试题 03.02. 栈的最小值
    // 请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。
    // 执行push、pop和min操作的时间复杂度必须为O(1)。

    // 方法一：辅助栈-时间复杂度：O(1)，空间复杂度：O(n)
    class MinStack {
        Deque<Integer> xStack;
        Deque<Integer> minStack;

        public MinStack() {
            xStack = new LinkedList<Integer>();
            minStack = new LinkedList<Integer>();
            minStack.push(Integer.MAX_VALUE);
        }

        public void push(int x) {
            xStack.push(x);
            minStack.push(Math.min(minStack.peek(), x));
        }

        public void pop() {
            xStack.pop();
            minStack.pop();
        }

        public int top() {
            return xStack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }

    // 面试题 03.03. 堆盘子
    // 设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。
    // 请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。
    // 此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。
    // 进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。
    // 当某个栈为空时，应当删除该栈。（即撤掉空盘，后续盘子下标减一）
    // 当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1.

    // 方法一：（自己写的）模拟-时间复杂度：O(n)，空间复杂度：O(n)
    class StackOfPlates {
        int stkSize;
        List<Deque<Integer>> list = new ArrayList<>();

        public StackOfPlates(int cap) {
            stkSize = cap;
        }

        public void push(int val) {
            // 盘子容量为0
            if (stkSize == 0)
                return;

            // 栈非空，且栈顶盘子未满
            if (!list.isEmpty() && list.get(list.size() - 1).size() < stkSize)
                list.get(list.size() - 1).push(val);
            else {// 栈顶盘子已满，或者栈为空
                Deque<Integer> stk = new ArrayDeque<>();
                stk.push(val);
                list.add(stk);
            }
        }

        public int pop() {
            if (list.isEmpty())
                return -1;
            else
                return popAt(list.size() - 1);
        }

        public int popAt(int index) {
            // 不存在该栈
            if (index < 0 || index >= list.size())
                return -1;
            Deque<Integer> stk = list.get(index);
            int ans = stk.pop();
            // 撤掉空盘
            if (stk.isEmpty())
                list.remove(index);
            return ans;
        }
    }

    // 面试题 03.04. 化栈为队
    // 实现一个MyQueue类，该类用两个栈来实现一个队列。
    // 说明：
    // 你只能使用标准的栈操作，也就是只有 push to top, peek/pop from top, size 和 is empty 操作是合法的。
    // 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
    // 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

    // 方法一：两个栈分别负责进出-时间复杂度：O(1)，空间复杂度：O(n)
    class MyQueue {
        Deque<Integer> stkIn = new ArrayDeque<>();
        Deque<Integer> stkOut = new ArrayDeque<>();

        public MyQueue() {

        }

        public void push(int x) {
            stkIn.push(x);
        }

        public int pop() {
            if (!stkOut.isEmpty())
                return stkOut.pop();

            while (!stkIn.isEmpty())
                stkOut.push(stkIn.pop());
            return stkOut.pop();
        }

        public int peek() {
            if (stkOut.isEmpty())
                while (!stkIn.isEmpty())
                    stkOut.push(stkIn.pop());

            return stkOut.peek();
        }

        public boolean empty() {
            return stkIn.isEmpty() && stkOut.isEmpty();
        }
    }

    // 面试题 03.05. 栈排序
    // 栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。
    // 最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。
    // 该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。

    // 方法一：（自己写的）辅助栈-时间复杂度：O(n2)，空间复杂度：O(n)
    // 每次入栈操作的时间复杂度为O(n)
    class SortedStack {
        Deque<Integer> stk = new ArrayDeque<>();
        Deque<Integer> supstk = new ArrayDeque<>();

        public SortedStack() {
        }

        public void push(int val) {
            if (stk.isEmpty()) {
                stk.push(val);
                return;
            }

            while (!stk.isEmpty() && stk.peek() < val)
                supstk.push(stk.pop());
            stk.push(val);
            while (!supstk.isEmpty())
                stk.push(supstk.pop());
        }

        public void pop() {
            if (!stk.isEmpty())
                stk.pop();
        }

        public int peek() {
            if (!stk.isEmpty())
                return stk.peek();
            return -1;
        }

        public boolean isEmpty() {
            return stk.isEmpty();
        }
    }

    // 方法二：（自己写的）不使用辅助栈，递归隐式栈-时间复杂度：O(n2)，空间复杂度：O(n)
    class SortedStack2 {
        Deque<Integer> stk = new ArrayDeque<>();

        public SortedStack2() {
        }

        public void push(int val) {
            dfs(val);
        }

        private void dfs(int val) {
            if (stk.isEmpty() || stk.peek() >= val) {
                stk.push(val);
                return;
            }

            int cur = stk.pop();
            dfs(val);
            stk.push(cur);
        }

        public void pop() {
            if (!stk.isEmpty())
                stk.pop();
        }

        public int peek() {
            if (!stk.isEmpty())
                return stk.peek();
            return -1;
        }

        public boolean isEmpty() {
            return stk.isEmpty();
        }
    }

    // 面试题 03.06. 动物收容所

    // 方法一：（自己写的）双队列-时间复杂度：O(n)，空间复杂度：O(n)
    class AnimalShelf {
        Queue<int[]> dogs = new LinkedList<>();
        Queue<int[]> cats = new LinkedList<>();
        int order = 0;

        public AnimalShelf() {
        }

        public void enqueue(int[] animal) {
            if (animal[1] == 0)
                cats.offer(animal);
            else
                dogs.offer(animal);
            animal[1] = order++;
        }

        public int[] dequeueAny() {
            if (dogs.isEmpty() && cats.isEmpty())
                return new int[] { -1, -1 };

            int dogOrder = dogs.isEmpty() ? Integer.MAX_VALUE : dogs.peek()[1];
            int catOrder = cats.isEmpty() ? Integer.MAX_VALUE : cats.peek()[1];

            if (catOrder < dogOrder) {
                int[] cat = cats.poll();
                cat[1] = 0;
                return cat;
            } else {
                int[] dog = dogs.poll();
                dog[1] = 1;
                return dog;
            }
        }

        public int[] dequeueDog() {
            if (dogs.isEmpty())
                return new int[] { -1, -1 };
            int[] dog = dogs.poll();
            dog[1] = 1;
            return dog;
        }

        public int[] dequeueCat() {
            if (cats.isEmpty())
                return new int[] { -1, -1 };
            int[] cat = cats.poll();
            cat[1] = 0;
            return cat;
        }
    }

    // 方法二：（自己写的）双队列 + LinkedHashSet 记录顺序，其实不如入队时在动物自身上记录order

    // 面试题 04.01. 节点间通路
    // 节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
    // 提示：
    // 节点数量n在[0, 1e5]范围内。
    // 节点编号大于等于 0 小于 n。
    // 图中可能存在自环和平行边。

    // 方法一：（自己写的）dfs
    // 这种结构存储边，主要还是为了去除自环和平行边
    List<Set<Integer>> edges = new ArrayList<>();
    boolean[] visited;
    int target;

    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        if (start == target)
            return true;

        visited = new boolean[n + 1];
        this.target = target;
        for (int i = 0; i <= n; i++)
            edges.add(new HashSet<>());

        for (int[] edge : graph) {
            int node1 = edge[0];
            int node2 = edge[1];
            if (node1 == node2)
                continue;
            edges.get(node1).add(node2);
        }
        return dfs(start);
    }

    private boolean dfs(int curr) {
        if (curr == target)
            return true;
        visited[curr] = true;
        for (int next : edges.get(curr))
            if (!visited[next] && dfs(next))
                return true;
        return false;
    }

    // 方法二：（自己写的）bfs
    public boolean findWhetherExistsPath2(int n, int[][] graph, int start, int target) {
        if (start == target)
            return true;

        List<Set<Integer>> edges = new ArrayList<>();
        boolean[] visited = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            edges.add(new HashSet<>());

        for (int[] edge : graph) {
            int node1 = edge[0];
            int node2 = edge[1];
            if (node1 == node2)
                continue;
            edges.get(node1).add(node2);
        }

        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int next : edges.get(curr)) {
                if (visited[next])
                    continue;
                if (next == target)
                    return true;
                queue.offer(next);
                visited[next] = true;
            }
        }
        return false;
    }

    // 面试题 04.02. 最小高度树
    // 给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

    // 方法一：中序遍历
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right)
            return null;

        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }

    // 面试题 04.03. 特定深度节点链表
    // 给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。
    // 返回一个包含所有深度的链表的数组。

    // 方法一：（自己写的）bfs
    public ListNode[] listOfDepth(TreeNode tree) {
        List<ListNode> res = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(tree);
        while (!queue.isEmpty()) {
            int n = queue.size();
            ListNode dummyHead = new ListNode(-1);
            ListNode prev = dummyHead;
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
                prev.next = new ListNode(node.val);
                prev = prev.next;
            }
            res.add(dummyHead.next);
        }
        return res.toArray(new ListNode[res.size()]);
    }

    // 面试题 04.04. 检查平衡性
    // 实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。

    // 方法一：自顶向下的递归
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;
        else
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left)
                    && isBalanced(root.right);
    }

    public int height(TreeNode root) {
        if (root == null)
            return 0;
        else
            return Math.max(height(root.left), height(root.right)) + 1;
    }

    // 方法二：自底向上的递归
    public boolean isBalanced2(TreeNode root) {
        return height2(root) >= 0;
    }

    public int height2(TreeNode root) {
        if (root == null)
            return 0;

        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1)
            return -1;
        else
            return Math.max(leftHeight, rightHeight) + 1;
    }

    // 方法二：（自己写的）自底向上的递归
    boolean flag = true;

    public boolean isBalanced22(TreeNode root) {
        dfs(root);
        return flag;
    }

    private int dfs(TreeNode root) {
        if (root == null)
            return 0;
        if (!flag)
            return -1;
        int leftDepth = dfs(root.left);
        int rightDepth = dfs(root.right);
        if (Math.abs(leftDepth - rightDepth) > 1) {
            flag = false;
            return -1;
        }
        return Math.max(leftDepth, rightDepth) + 1;
    }

    // 面试题 04.05. 合法二叉搜索树

    // 方法一：递归-时间复杂度：O(n)，空间复杂度：O(n)
    // 实现一个函数，检查一棵二叉树是否为二叉搜索树。
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }

    public boolean helper(TreeNode node, Integer lower, Integer upper) {
        if (node == null)
            return true;

        int val = node.val;
        if (lower != null && val <= lower)
            return false;

        if (upper != null && val >= upper)
            return false;

        if (!helper(node.right, val, upper))
            return false;

        if (!helper(node.left, lower, val))
            return false;

        return true;
    }

    // 方法二：中序遍历（迭代）-时间复杂度：O(n)，空间复杂度：O(n)
    public boolean isValidBST2(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        double inorder = -Double.MAX_VALUE;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root.val <= inorder)
                return false;

            inorder = root.val;
            root = root.right;
        }
        return true;
    }

    // 方法二：（自己写的）中序遍历（递归）-时间复杂度：O(n)，空间复杂度：O(n)
    long prev = Long.MIN_VALUE;
    boolean isValid = true;

    public boolean isValidBST22(TreeNode root) {
        dfs22(root);
        return isValid;
    }

    private void dfs22(TreeNode root) {
        if (root == null || !isValid)
            return;
        dfs22(root.left);
        if (root.val <= prev) {
            isValid = false;
            return;
        }
        prev = root.val;
        dfs22(root.right);
    }

    // 面试题 04.06. 后继者
    // 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
    // 如果指定节点没有对应的“下一个”节点，则返回null。

    // 方法一：利用二叉搜索树的性质-时间复杂度：O(logn)（数退化成链表时则为O(n)），空间复杂度：O(1)
    // 如果节点 p 的右子树不为空，则节点 p 的后继节点在其右子树中，在其右子树中定位到最左边的节点，即为节点 p 的后继节点。
    // 如果节点 p 的右子树为空，则需要从根节点开始遍历寻找节点 p 的祖先节点。
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        if (p.right != null) {
            successor = p.right;
            while (successor.left != null)
                successor = successor.left;
            return successor;
        }
        TreeNode node = root;
        while (node != null) {
            if (node.val > p.val) {
                successor = node;
                node = node.left;
            } else
                node = node.right;
        }
        return successor;
    }

    // 方法一：（自己写的）利用二叉搜索树的性质-时间复杂度：O(logn)（数退化成链表时则为O(n)），空间复杂度：O(1)
    // 寻找后继节点，记录最小的后继节点
    public TreeNode inorderSuccessor11(TreeNode root, TreeNode p) {
        int target = p.val + 1;
        TreeNode res = null;
        while (root != null) {
            if (root.val >= target) {
                res = root;
                root = root.left;
            } else
                root = root.right;
        }
        return res;
    }

    // 方法二：中序遍历
    public TreeNode inorderSuccessor2(TreeNode root, TreeNode p) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        TreeNode prev = null, curr = root;
        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (prev == p)
                return curr;

            prev = curr;
            curr = curr.right;
        }
        return null;
    }

    // 面试题 04.08. 首个共同祖先
    // 设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。
    // 注意：这不一定是二叉搜索树。
    // 说明:
    // 所有节点的值都是唯一的。
    // p、q 为不同节点且均存在于给定的二叉树中。

    // 方法一：dfs-时间复杂度：O(n)，空间复杂度：O(n)
    private TreeNode ans;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return ans;
    }

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return false;
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson)))
            ans = root;

        return lson || rson || (root.val == p.val || root.val == q.val);
    }

    // 方法一：（自己写的）dfs-时间复杂度：O(n)，空间复杂度：O(n)
    TreeNode p, q, res;

    public TreeNode lowestCommonAncestor11(TreeNode root, TreeNode p, TreeNode q) {
        this.p = p;
        this.q = q;
        dfs11(root);
        return res;
    }

    // 找到公共节点时，随便返回 true or fals，后续节点也不可能再找到公共节点
    private boolean dfs11(TreeNode root) {
        if (root == null)
            return false;
        boolean left = dfs11(root.left);
        boolean right = dfs11(root.right);
        if (left && right)// p q 分别位于左右子树
            res = root;
        else if (left || right) {// 左右子树只有一个
            if (root == p || root == q)// 当前为 p 或 q
                res = root;
            return true;
        } else {// 左右子树没有 p q
            if (root == p || root == q)
                return true;
        }
        return false;
    }

    // 方法二：（自己写的）遍历-时间复杂度：O(n)，空间复杂度：O(n)
    // TreeNode p, q;
    List<TreeNode> list = new ArrayList<>();
    List<TreeNode> listp, listq;

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        this.p = p;
        this.q = q;
        getPath(root);
        TreeNode res = null;
        for (int i = 0; i < Math.min(listp.size(), listq.size()); i++) {
            if (listp.get(i) != listq.get(i))
                break;
            res = listp.get(i);
        }
        return res;
    }

    private void getPath(TreeNode root) {
        if (root == null)
            return;

        list.add(root);
        if (root == p)
            listp = new ArrayList<>(list);
        if (root == q)
            listq = new ArrayList<>(list);

        getPath(root.left);
        getPath(root.right);
        list.remove(list.size() - 1);
    }

    // 面试题 04.09. 二叉搜索树序列
    // 从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。
    // （生成二叉搜索树，此时不要求只访问一次根节点，每次插入都可以从根节点开始向下寻找插入位置）
    // 给定一个由不同节点组成的二叉搜索树 root，输出所有可能生成此树的数组。
    // 提示：
    // 二叉搜索树中的节点数在 [0, 1000] 的范围内
    // 1 <= 节点值 <= 10^6
    // 用例保证符合要求的数组数量不超过 5000

    // 题目示例太简单了，没有揭示隐藏题意
    // 隐藏题意：所有可能生成此树的数组，即是遍历这棵二叉树的所有方式
    // 考虑常规的dfs bfs 遍历树太麻烦了（重复、遍历顺序等问题）
    // 可以用一种巧妙的基于列表或集合（表示当前可见节点，或可插入节点）实现的方式（这里数据结构选择列表效率更高，回溯的还原更省时间）
    // 启发点：每一个节点都必须排在它的子孙结点前面

    // 方法一：（自己写的）回溯（维护一个当前可见节点，或可插入节点的数据结构）
    // 主要难点在于在遍历数据结构的同时要对其进行修改，java 的List Set 在增强for循环时不允许被修改或引用
    List<TreeNode> next = new ArrayList<>();
    List<Integer> ans0409 = new ArrayList<>();
    List<List<Integer>> res0409 = new ArrayList<>();

    public List<List<Integer>> BSTSequences(TreeNode root) {
        if (root != null)
            next.add(root);
        dfs();
        return res0409;
    }

    private void dfs() {
        if (next.isEmpty()) {
            res0409.add(new ArrayList<>(ans0409));
            return;
        }

        List<TreeNode> copy = new ArrayList<>(next);
        for (TreeNode curr : copy) {
            ans0409.add(curr.val);
            next.remove(curr);
            if (curr.left != null)
                next.add(curr.left);
            if (curr.right != null)
                next.add(curr.right);
            dfs();
            ans0409.remove(ans0409.size() - 1);
            // 回溯中还原的本质，进入下一层dfs之前的操作全部还原，前后操作对称
            // 直接简单粗暴的还原为方便遍历的拷贝，直接next = copy 也是不行的，正在遍历的copy无法被其他变量引用
            next = new ArrayList<>(copy);

            // 操作对称的还原
            // next.add(curr);
            // if (curr.left != null)
            // next.remove(curr.left);
            // if (curr.right != null)
            // next.remove(curr.right);
        }
    }

    // 面试题 04.10. 检查子树
    // 检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。
    // 如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。
    // 注意：此题相对书上原题略有改动。
    // 提示：
    // 树的节点数目范围为[0, 20000]。

    // 方法一：（自己写的）双重 dfs-时间复杂度：O(n2)，空间复杂度：O(n)
    // boolean flag = false;
    TreeNode t1, t2;

    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
        this.t1 = t1;
        this.t2 = t2;

        dfs0410(t1);
        return flag;
    }

    private void dfs0410(TreeNode root) {
        if (root == null || flag)
            return;

        if (compare(root, t2))
            flag = true;
        dfs0410(root.left);
        dfs0410(root.right);
    }

    private boolean compare(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null)
            return true;
        if (root1 == null || root2 == null)
            return false;
        if (root1.val != root2.val)
            return false;
        boolean left = compare(root1.left, root2.left);
        boolean right = compare(root1.right, root2.right);
        return left && right;
    }

    // 方法二：（自己写的）比较遍历序列-时间复杂度：O(n)，空间复杂度：O(n)
    // 实际效率比方法一还差，可见方法一的实际复杂度是接近O(n)的
    // 这个好像和树哈希类似
    public boolean checkSubTree2(TreeNode t1, TreeNode t2) {
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        dfs(t1, sb1);
        dfs(t2, sb2);
        String str1 = sb1.toString();
        String str2 = sb2.toString();
        if (str1.contains(str2))
            return true;
        return false;
    }

    private void dfs(TreeNode root, StringBuilder sb) {
        if (root == null)
            return;
        sb.append(root.val);
        sb.append(",");
        dfs(root.left, sb);
        dfs(root.right, sb);
    }

    // 面试题 04.12. 求和路径
    // 给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。
    // 设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。
    // 注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。

    // 方法一: 前缀和-时间复杂度：O(n)，空间复杂度：O(n)
    public int pathSum(TreeNode root, int sum) {
        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
        prefix.put(0L, 1);// 方便求出从头节点开始的路径
        return dfs(root, prefix, 0, sum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int sum) {
        if (root == null)
            return 0;

        int ret = 0;
        curr += root.val;

        ret = prefix.getOrDefault(curr - sum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        ret += dfs(root.left, prefix, curr, sum);
        ret += dfs(root.right, prefix, curr, sum);

        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);// 还原操作
        return ret;
    }

    // 方法一：（自己写的）前缀和-时间复杂度：O(n)，空间复杂度：O(n)
    int cur = 0, sum = 0;
    int res0412 = 0;
    Map<Integer, Integer> map = new HashMap<>();

    public int pathSum11(TreeNode root, int sum) {
        this.sum = sum;
        map.put(0, 1);
        dfs0412(root);
        return res0412;
    }

    private void dfs0412(TreeNode root) {
        if (root == null)
            return;

        // 求路径数的操作是有顺序的
        cur += root.val;
        res0412 += map.getOrDefault(cur - sum, 0);
        map.put(cur, map.getOrDefault(cur, 0) + 1);
        dfs0412(root.left);
        dfs0412(root.right);

        // 还原操作也是有顺序的（严格按照dfs前的反向操作）
        map.put(cur, map.get(cur) - 1);
        cur -= root.val;
    }

    // 方法二：双重 dfs-时间复杂度：O(n2)，空间复杂度：O(n)
    public int pathSum2(TreeNode root, int sum) {
        if (root == null)
            return 0;

        int ret = rootSum(root, sum);
        ret += pathSum(root.left, sum);
        ret += pathSum(root.right, sum);
        return ret;
    }

    public int rootSum(TreeNode root, int sum) {
        int ret = 0;

        if (root == null)
            return 0;

        int val = root.val;
        if (val == sum)
            ret++;

        ret += rootSum(root.left, sum - val);
        ret += rootSum(root.right, sum - val);
        return ret;
    }

    // 面试题 05.01. 插入
    // 给定两个整型数字 N 与 M，以及表示比特位置的 i 与 j（i <= j，且从 0 位开始计算）。
    // 编写一种方法，使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~ j 位区域，不足之处用 0 补齐。具体插入过程如图所示。
    // 题目保证从 i 位到 j 位足以容纳 M， 例如： M = 10011，则 i～j 区域至少可容纳 5 位。

    // 方法一：位运算（整体操作，无循环）-时间复杂度：O(1)，空间复杂度：O(1)
    // 1. 先把数N的j到i之间的位置0，2. M左移i位，3. 再用N或运算M
    public int insertBits(int N, int M, int i, int j) {
        // 1左移x位再减1，末尾x位为1
        int mask = ~(((1 << (j - i + 1)) - 1) << i);
        N &= mask;// 1. 先把数N的j到i之间的位置0
        M = M << i;// 2. M左移i位
        return M | N;// 3. 再用N或运算M
    }

    // 方法一：（自己写的）位运算（逐位操作，有循环）
    public int insertBits11(int N, int M, int i, int j) {
        for (int NBit = i; NBit <= j; NBit++) {
            int MBit = NBit - i; // 处理M的第MBit位

            int mask = 1 << NBit;
            if (((M >> MBit) & 1) == 1)
                N = N | mask;// 置为1 | 000010
            else
                N = N & ~mask;// 置为0 & 111101
        }
        return N;
    }

    // 面试题 05.02. 二进制数转字符串
    // 二进制数转字符串。给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表达式。
    // 如果该数字无法精确地用32位以内的二进制表示，则打印“ERROR”。

    // 方法一：循环乘以2
    // 思路：十进制的小数转换为二进制小数，主要是利用小数部分乘2后，取整数部分，直至小数点后为0
    public String printBin(double num) {
        StringBuilder res = new StringBuilder("0.");
        while (num != 0) {
            num *= 2;
            if (num >= 1) { // 乘2后num>=1,说明此时整数部分为1，取完该整数部分1后，num接着利用的还是其小数部分，所以要减掉整数部分（即1）
                res.append("1");
                num -= 1;
            } else // 小于1说明整数部分为0，取该整数部分0
                res.append("0");

            if (res.length() > 32)
                return "ERROR";
        }
        return res.toString();
    }

    // 方法二：（自己写的）循环减值
    public String printBin2(double num) {
        StringBuilder res = new StringBuilder("0.");
        double var = 1.0 / 2;
        for (int i = 0; i < 30; i++) {
            if (num >= var) {
                num -= var;
                res.append("1");
            } else
                res.append("0");
            var = var / 2;
            if (num == 0.0)
                break;
        }
        if (num == 0.0)
            return res.toString();
        return "ERROR";
    }

    // 面试题 05.03. 翻转数位
    // 给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。

    // 方法一：动态规划-时间复杂度：O(n)，空间复杂度：O(1)，n=32
    public int reverseBits(int num) {
        int onesBeforeZero = 0;// 记录0之前的1的个数
        int onesAfterZero = 0;// 记录0之后的1的个数
        int res = 0;
        for (int i = 0; i++ < 32; num >>= 1) {
            if ((num & 1) == 1)
                ++onesAfterZero;
            else {
                onesBeforeZero = onesAfterZero;
                onesAfterZero = 0;
            }
            res = Math.max(onesBeforeZero + onesAfterZero + 1, res);
        }
        return res == 33 ? 32 : res;
    }

    // 方法二：（自己写的）两次遍历-时间复杂度：O(n)，空间复杂度：O(n)，n=32
    public int reverseBits2(int num) {
        int[] left = new int[32];
        int[] right = new int[32];
        int ones = 0;
        for (int i = 0; i < 32; i++) {
            left[i] = ones;
            int bit = 32 - i - 1;
            if ((num & (1 << bit)) == 0)
                ones = 0;
            else
                ones++;
        }

        ones = 0;
        for (int i = 31; i >= 0; i--) {
            right[i] = ones;
            int bit = 32 - i - 1;
            if ((num & (1 << bit)) == 0)
                ones = 0;
            else
                ones++;
        }

        int res = 1;
        for (int i = 0; i < 32; i++)
            res = Math.max(res, left[i] + right[i] + 1);
        return res;
    }

    // 面试题 05.04. 下一个数
    // 下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。
    // 提示:
    // num的范围在[1, 2147483647]之间；
    // 如果找不到前一个或者后一个满足条件的正数，那么输出 -1。
    // 可以参考字典序法

    // 方法一：位运算-时间复杂度：O(1)，空间复杂度：O(1)
    // 比 num 大的数：从右往左，找到第一个 01 位置，然后把 01 转为 10，右侧剩下的 1 移到右侧的低位，右侧剩下的位清0。
    // 比 num 小的数：从右往左，找到第一个 10 位置，然后把 10 转为 01，右侧剩下的 1 移到右侧的高位，右侧剩下的位置0。
    public int[] findClosedNumbers(int num) {
        int count = 0;// 记录1的数量
        int big = -1, small = -1;
        int numTmp = num;
        for (int i = 0; i < 30; i++) {
            // 遇到01，把他变为10，并且把右侧的1放到最右边
            if ((num & (1 << i)) != 0 && (num & (1 << i + 1)) == 0) {
                numTmp += (1 << i + 1);
                numTmp -= (1 << i);
                for (int j = 0; j < count; j++)
                    numTmp += (1 << j);

                big = numTmp;
                break;
            }
            if ((num & (1 << i)) != 0)
                count++;
            numTmp &= (~(1 << i));
        }
        numTmp = num;
        count = 0;
        for (int i = 0; i < 30; i++) {
            // 遇到10，把他变为01，并且把右侧的1放到最左边
            if ((num & (1 << i)) == 0 && (num & (1 << i + 1)) != 0) {
                numTmp -= (1 << i + 1);
                numTmp += (1 << i);
                for (int j = 0; j < count; j++)
                    numTmp += (1 << i - j - 1);

                small = numTmp;
                break;
            }
            if ((num & (1 << i)) != 0)
                count++;
            numTmp &= (~(1 << i));
        }
        return new int[] { big, small };
    }

    // 方法一：（自己写的）位运算-时间复杂度：O(1)，空间复杂度：O(1)
    /**
     * 
     * @param rightOnesRight  0111]00 0111011] 最右侧连续1的右边界
     * @param rightOnesLeft   0[11100 01110[11 最右侧连续1的左边界
     * @param secondOnesRight 0111]011 指这一段1
     * 
     * @return
     */
    // 32位 最低位记为0，最高位31为符号位，正整数区间为30至0，则最大值为 2^31-1 = 2147483647
    public int[] findClosedNumbers2(int num) {
        int[] res = new int[2];

        int rightOnesRight = 0;
        for (; rightOnesRight < 31; rightOnesRight++)
            if ((num & (1 << rightOnesRight)) != 0)
                break;
        int rightOnesLeft = rightOnesRight;
        for (; rightOnesLeft < 31; rightOnesLeft++)
            if ((num & (1 << rightOnesLeft)) == 0)
                break;
        rightOnesLeft--;

        if (rightOnesLeft == 30)// 没有更大的满足条件的正数
            res[0] = -1;
        else {
            int ans = num;
            // 删除最右边的一部分1方便后续操作
            for (int i = rightOnesRight; i <= rightOnesLeft; i++)
                ans &= ans - 1;

            ans = ans | (1 << (rightOnesLeft + 1));
            int mask = (1 << (rightOnesLeft - rightOnesRight)) - 1;
            ans = ans | mask;
            res[0] = ans;
        }

        if (rightOnesRight == 0) {// 最右侧连续从最低位就开始了，此时要判断是否有更小的满足条件的正数
            int secondOnesRight = rightOnesLeft + 1;
            for (; secondOnesRight < 31; secondOnesRight++)
                if ((num & (1 << secondOnesRight)) != 0)
                    break;

            if (secondOnesRight == 31)// 没有更小的满足条件的正数
                res[1] = -1;
            else {
                int ans = num;
                // 删除最右边的一部分1方便后续操作
                for (int i = rightOnesRight; i <= rightOnesLeft + 1; i++)
                    ans &= ans - 1;
                int operateOnes = rightOnesLeft - rightOnesRight + 1 + 1;// 需要操作的1的个数
                int mask = ((1 << (operateOnes)) - 1) << (secondOnesRight - operateOnes);
                ans = ans | mask;
                res[1] = ans;
            }
        } else {
            int ans = num;
            ans &= ans - 1;
            int mask = 1 << (rightOnesRight - 1);
            ans = ans | mask;
            res[1] = ans;
        }
        return res;
    }

    // 面试题 05.06. 整数转换
    // 整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。
    // 提示:
    // A，B范围在[-2147483648, 2147483647]之间

    // 方法一：（自己写的）异或 + Brian Kernighan 算法-时间复杂度：O(1)，空间复杂度：O(1)
    public int convertInteger(int A, int B) {
        int xor = A ^ B;
        int res = 0;
        while (xor != 0) {
            xor &= xor - 1;
            res++;
        }
        return res;
    }

    // 面试题 05.07. 配对交换
    // 配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位0与位1交换，位2与位3交换，以此类推）
    // 提示:
    // num的范围在[0, 2^30 - 1]之间，不会发生整数溢出。

    // 方法一：位运算-时间复杂度：O(n)，空间复杂度：O(1)
    // 思路：分别取出奇数位和偶数位，移动后做或运算
    public int exchangeBits(int num) {
        int odd = num & 0x55555555;// 取奇数位 0x55555555 = 0b0101_0101_0101_0101_0101_0101_0101_0101
        int even = num & 0xaaaaaaaa;// 取偶数位 0xaaaaaaaa = 0b1010_1010_1010_1010_1010_1010_1010_1010
        odd = odd << 1;
        even = even >> 1;
        return odd | even;
    }

    // 方法一：（自己写的）位运算
    // 逐组交换 1↔0, 3↔2...
    public int exchangeBits2(int num) {
        for (int even = 0; even <= 30; even += 2) {
            int odd = even + 1;
            int evenBit = (1 << even) & num;
            int oddBit = (1 << odd) & num;
            if (evenBit == 0 && oddBit == 0 || evenBit != 0 && oddBit != 0)// 奇偶位相同，无需交换
                continue;
            if (evenBit != 0) {// 奇数位置1，偶数位置0
                num = num | (evenBit << 1);
                num = num & ~evenBit;
            }
            if (oddBit != 0) {// 偶数位置1，奇数位置0
                num = num | (oddBit >> 1);
                num = num & ~oddBit;
            }
        }
        return num;
    }

    // 面试题 05.08. 绘制直线
    // 已知一个由像素点组成的单色屏幕，每行均有 w 个像素点，所有像素点初始为 0，左上角位置为 (0,0)。
    // 现将每行的像素点按照「每 32 个像素点」为一组存放在一个 int 中，再依次存入长度为 length 的一维数组中。
    // 我们将在屏幕上绘制一条从点 (x1,y) 到点 (x2,y) 的直线（即像素点修改为 1），请返回绘制过后的数组。
    // 注意：
    // 用例保证屏幕宽度 w 可被 32 整除（即一个 int 不会分布在两行上）
    // 提示：
    // 1 <= length <= 10^5
    // 1 <= w <= 3 * 10^5
    // 0 <= x1 <= x2 < w
    // 0 <= y <= 10

    // length：表示int的总数，一个int32位，换句话说就是总共有length*32位二进制数
    // w: 表示一行二进制位数，题目说了w能被32整除，也就是一行有w/32个int
    // y: 表示在哪一行画直线
    // x1：表示从行y开始下标为x1的二进制开始画
    // x2：表示画到行y下标为x2的二进制

    // 方法一：位运算-时间复杂度：O(1)，空间复杂度：O(1)
    // e.g. ...000[0001111..1][11111...1][111...1100]000...
    public int[] drawLine(int length, int w, int x1, int x2, int y) {
        int[] ans = new int[length];
        // 计算含有1的数的下标
        int low = (y * w + x1) / 32;
        int high = (y * w + x2) / 32;
        // 这些下标区间内的数的全部位置为1
        for (int i = low; i <= high; i++)
            ans[i] = -1;
        // 额外修改左右边界的数即可
        ans[low] = ans[low] >>> x1 % 32;
        ans[high] = ans[high] & Integer.MIN_VALUE >> x2 % 32;
        return ans;
    }

    // 方法一：（自己写的）位运算（分情况讨论）-时间复杂度：O(1)，空间复杂度：O(1)
    public int[] drawLine2(int length, int w, int x1, int x2, int y) {
        int[] res = new int[length];
        int currLength = 0;
        int ymax = length * 32 / w;
        for (int i = 0; i < ymax; i++) {// 第i行
            for (int j = 0; j < w / 32; j++) {// 第j个拆分的int
                if (i != y) {
                    res[currLength++] = 0;
                    continue;
                }
                int min = 32 * j;
                int max = 32 * (j + 1) - 1;
                int ans = 0;
                // 直线覆盖整个区间[min, max]
                if (x1 <= min && max <= x2)
                    ans = -1;
                // 区间[min, max]不在直线内
                else if (min > x2 || max < x1)
                    ans = 0;
                // 区间内[x1, x2]置1
                else if (min <= x1 && x1 <= max && min <= x2 && x2 <= max)
                    for (int bit = x1 % 32; bit <= x2 % 32; bit++)
                        ans = ans | (Integer.MIN_VALUE >>> bit);// 注意：最高位要补1而不是0！
                // 直线[x1, max]置1
                else if (min <= x1 && x1 <= max)
                    for (int bit = x1 % 32; bit < 32; bit++)
                        ans = ans | (Integer.MIN_VALUE >>> bit);
                // 直线[min, x2]置1
                else if (min <= x2 && x2 <= max)
                    for (int bit = 0; bit <= x2 % 32; bit++)
                        ans = ans | (Integer.MIN_VALUE >>> bit);
                res[currLength++] = ans;
            }
        }
        return res;
    }

    // 面试题 08.01. 三步问题
    // 三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。
    // 结果可能很大，你需要对结果模1000000007。
    // 提示:
    // n范围在[1, 1000000]之间

    // 方法一：（自己写的）动态规划 + 滚动数组-时间复杂度：O(n)，空间复杂度：O(1)
    public int waysToStep(int n) {
        if (n < 3)
            return n;
        int dp1 = 1, dp2 = 1, dp3 = 2;
        for (int i = 3; i <= n; i++) {
            int next = ((dp1 + dp2) % 1000000007 + dp3) % 1000000007;
            dp1 = dp2;
            dp2 = dp3;
            dp3 = next;
        }
        return dp3;
    }

    // 方法二：递归 + 记忆化搜索-时间复杂度：O(n)，空间复杂度：O(n)

    // 方法三：矩阵求解 + 快速幂-时间复杂度：O(n)，空间复杂度：O(1)

    // 面试题 08.02. 迷路的机器人
    // 设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。
    // 设计一种算法，寻找机器人从左上角移动到右下角的路径。
    // 网格中的障碍物和空位置分别用 1 和 0 来表示。
    // 返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径，返回空数组。
    // 说明：r 和 c 的值均不超过 100。

    // 方法一：（自己写的）dfs + 记忆化搜索
    List<List<Integer>> res0802 = new ArrayList<>();
    List<List<Integer>> ans0802 = new ArrayList<>();
    int[][] obstacleGrid;
    boolean[][] deadend;
    boolean find = false;
    int m, n;

    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        this.obstacleGrid = obstacleGrid;
        this.m = obstacleGrid.length;
        this.n = obstacleGrid[0].length;
        deadend = new boolean[m][n];
        if (obstacleGrid[0][0] == 0)
            dfs(0, 0);
        return res0802;
    }

    private void dfs(int x, int y) {
        if (find)
            return;
        List<Integer> temp = new ArrayList<>();
        temp.add(x);
        temp.add(y);
        ans0802.add(temp);
        if (x == m - 1 && y == n - 1) {
            res0802 = new ArrayList<>(ans0802);
            find = true;
            return;
        }
        int[][] directions = new int[][] { { 1, 0 }, { 0, 1 } };
        for (int[] direction : directions) {
            int newx = x + direction[0];
            int newy = y + direction[1];
            if (newx >= m || newy >= n || obstacleGrid[newx][newy] == 1 || deadend[newx][newy])
                continue;
            dfs(newx, newy);
        }
        deadend[x][y] = true;
        ans0802.remove(ans0802.size() - 1);
    }

    // 方法二：动态规划（找到哪些点可达）再寻找可行路径

    // 面试题 08.03. 魔术索引
    // 魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。
    // 给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。
    // 若有多个魔术索引，返回索引值最小的一个。
    // 说明:
    // nums长度在[1, 1000000]之间
    // 此题为原书中的 Follow-up，即数组中可能包含重复元素的版本

    // 方法一：二分剪枝-时间复杂度：O(n)，空间复杂度：O(n)
    // 包含重复元素，就没必要强行二分了（原题是严格有序）

    // 方法二：顺序遍历 + 索引跳跃
    public int findMagicIndex2(int[] nums) {
        int index = 0;
        while (index < nums.length) {
            if (nums[index] == index)
                return index;
            if (nums[index] < index)
                index++;
            else// nums[index] > index 此时[index,
                // nums[index]-1]的值都小于nums[index]，直接跳到索引为nums[index]处
                index = nums[index];
        }
        return -1;
    }

    // 面试题 08.04. 幂集
    // 幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。
    // 说明：解集不能包含重复的子集。

    // 方法一：迭代法实现子集枚举（二进制表示子集）-时间复杂度：O(n2^n)，空间复杂度：O(n)
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans0804 = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i)
                if ((mask & (1 << i)) != 0)
                    t.add(nums[i]);
            ans0804.add(new ArrayList<Integer>(t));
        }
        return ans0804;
    }

    // 方法二：递归法实现子集枚举-时间复杂度：O(n2^n)，空间复杂度：O(n)
    // List<Integer> t = new ArrayList<Integer>();
    // List<List<Integer>> ans0804 = new ArrayList<List<Integer>>();
    public List<List<Integer>> subsets2(int[] nums) {
        dfs(0, nums);
        return ans0804;
    }

    public void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans0804.add(new ArrayList<Integer>(t));
            return;
        }
        t.add(nums[cur]);
        dfs(cur + 1, nums);
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }

    // 面试题 08.05. 递归乘法
    // 递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
    // 提示:
    // 保证乘法范围不会溢出

    // 方法一：快速乘（快速幂）-时间复杂度：O(logn)，空间复杂度：O(1)
    public int multiply(int A, int B) {
        if (A < B)
            return fastMultiply(B, A);
        return fastMultiply(A, B);
    }

    private int fastMultiply(int x, int y) {
        int res = 0;
        int base = x;
        while (y != 0) {
            if ((y & 1) == 1)
                res += base;
            base = base + base;
            y = y >> 1;
        }
        return res;
    }

    // 面试题 08.06. 汉诺塔问题
    // 在经典汉诺塔问题中，有 3 根柱子及 N
    // 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。
    // 一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
    // (1) 每次只能移动一个盘子;
    // (2) 盘子只能从柱子顶端滑出移到下一根柱子;
    // (3) 盘子只能叠在比它大的盘子上。
    // 请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
    // 你需要原地修改栈。

    // 方法一：dfs 分治-时间复杂度：O(2^n-1)，空间复杂度：O(1)
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A, B, C, A.size());
    }

    /**
     * 将A上的N个盘子（保持相对顺序）移动到C上
     * 
     * @param A
     * @param B
     * @param C
     * @param N
     */
    private void dfs(List<Integer> A, List<Integer> B, List<Integer> C, int N) {
        if (N == 0)
            return;
        dfs(A, C, B, N - 1);// 将A上的N-1个盘子（保持相对顺序）移动到B上

        // 将A上的最后一个盘子移动到C上
        int temp = A.remove(A.size() - 1);
        C.add(temp);

        dfs(B, A, C, N - 1);// 将B上的N-1个盘子（保持相对顺序）移动到C上
    }

    // 面试题 08.07. 无重复字符串的排列组合
    // 无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
    // 提示:
    // 字符都是英文字母。
    // 字符串长度在[1, 9]之间。

    // 方法一：（自己写的）dfs 回溯
    boolean[] used;
    String S;
    List<String> res0807 = new ArrayList<>();
    StringBuilder ans0807 = new StringBuilder();

    public String[] permutation(String S) {
        this.used = new boolean[S.length()];
        this.S = S;
        dfs0807(0);
        return res0807.toArray(new String[res0807.size()]);
    }

    private void dfs0807(int index) {
        if (index == S.length()) {
            res0807.add(new String(ans0807));
            return;
        }

        for (int i = 0; i < S.length(); i++) {
            if (used[i])
                continue;
            used[i] = true;
            ans0807.append(S.charAt(i));
            dfs0807(index + 1);
            used[i] = false;
            ans0807.deleteCharAt(ans0807.length() - 1);
        }
    }

    // 面试题 08.08. 有重复字符串的排列组合
    // 有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
    // 提示:
    // 字符都是英文字母。
    // 字符串长度在[1, 9]之间。

    // 方法一：（自己写的）dfs 回溯 + 排序避免重复
    char[] chars;
    boolean[] used0808;
    List<String> res0808 = new ArrayList<>();
    StringBuilder ans0808 = new StringBuilder();

    public String[] permutation0808(String S) {
        this.chars = S.toCharArray();
        this.used0808 = new boolean[S.length()];
        Arrays.sort(chars);
        dfs0808(0);
        return res0808.toArray(new String[res0808.size()]);
    }

    private void dfs0808(int index) {
        if (index == chars.length) {
            res0808.add(new String(ans0808));
            return;
        }

        for (int i = 0; i < chars.length; i++) {
            if (used0808[i])
                continue;
            if (i > 0 && chars[i] == chars[i - 1] && !used0808[i - 1])
                continue;
            used0808[i] = true;
            ans0808.append(chars[i]);
            dfs0808(index + 1);
            used0808[i] = false;
            ans0808.deleteCharAt(ans0808.length() - 1);
        }
    }

    // 面试题 08.09. 括号
    // 括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
    // 说明：解集不能包含重复的子集。

    // 方法一：（自己写的）dfs 回溯
    StringBuilder ans0809 = new StringBuilder();
    List<String> res0809 = new ArrayList<>();
    int n0809;

    public List<String> generateParenthesis(int n) {
        this.n0809 = n;
        dfs0809(0, 0);
        return res0809;
    }

    private void dfs0809(int left, int right) {
        if (left == n0809 && right == n0809) {
            res0809.add(new String(ans0809));
            return;
        }
        if (left < n0809) {
            ans0809.append('(');
            dfs0809(left + 1, right);
            ans0809.deleteCharAt(ans0809.length() - 1);
        }
        if (left > right) {
            ans0809.append(')');
            dfs0809(left, right + 1);
            ans0809.deleteCharAt(ans0809.length() - 1);
        }
    }

    // 方法二：按括号序列的长度递归-时间复杂度：略，空间复杂度：略
    // 任何一个括号序列都一定是由 ( 开头，并且第一个 ( 一定有一个唯一与之对应的 )。
    // 这样一来，每一个括号序列可以用 (a)b 来表示，其中 a 与 b 分别是一个合法的括号序列（可以为空）。
    @SuppressWarnings("unchecked")
    List<String>[] cache = new ArrayList[9];// 记忆化缓存 含有n个括号的所有括号组合，提示：1 <= n <= 8

    public List<String> generate(int n) {
        if (cache[n] != null) // 已经计算过cache[n]
            return cache[n];

        // 计算cache[n]
        ArrayList<String> ans = new ArrayList<String>();
        if (n == 0)
            ans.add("");
        else
            for (int c = 0; c < n; ++c)
                for (String left : generate(c))
                    for (String right : generate(n - 1 - c))
                        ans.add("(" + left + ")" + right);

        cache[n] = ans;
        return ans;
    }

    public List<String> generateParenthesis2(int n) {
        return generate(n);
    }

    // 方法三：暴力法-时间复杂度：O(2^{2n}n)，空间复杂度：O(n)
    // 我们可以生成所有 2^2n 个 '(' 和 ')' 字符构成的序列，然后我们检查每一个是否有效即可。

    // 面试题 08.10. 颜色填充
    // 编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。
    // 待填充的图像用二维数组 image 表示，元素为初始颜色值。初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor 。
    // 「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。
    // 请用新颜色填充初始坐标点的周围区域，并返回填充后的图像。
    // 提示：
    // image 和 image[0] 的长度均在范围 [1, 50] 内。
    // 初始坐标点 (sr,sc) 满足 0 <= sr < image.length 和 0 <= sc < image[0].length 。
    // image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535] 内。

    // 方法一：（自己写的）dfs
    int[][] image;
    boolean[][] visited0810;
    int initColor, newColor;

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        this.image = image;
        visited0810 = new boolean[image.length][image[0].length];
        this.initColor = image[sr][sc];
        this.newColor = newColor;
        dfs0810(sr, sc);
        return image;
    }

    private void dfs0810(int i, int j) {
        visited0810[i][j] = true;
        image[i][j] = newColor;
        int[][] directions = new int[][] { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        for (int[] direction : directions) {
            int newi = i + direction[0];
            int newj = j + direction[1];
            if (0 <= newi && newi < image.length && 0 <= newj && newj < image[0].length
                    && image[newi][newj] == initColor && !visited0810[newi][newj])
                dfs0810(newi, newj);
        }
    }

    // 方法二：bfs
    public int[][] floodFill2(int[][] image, int sr, int sc, int newColor) {
        int[] dx = { 1, 0, 0, -1 };
        int[] dy = { 0, 1, -1, 0 };
        int currColor = image[sr][sc];
        if (currColor == newColor)
            return image;

        int n = image.length, m = image[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[] { sr, sc });
        image[sr][sc] = newColor;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            for (int i = 0; i < 4; i++) {
                int mx = x + dx[i], my = y + dy[i];
                if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor) {
                    queue.offer(new int[] { mx, my });
                    image[mx][my] = newColor;
                }
            }
        }
        return image;
    }

    // 面试题 08.11. 硬币
    // 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
    // 0 <= n (总金额) <= 1000000
    // 这是一个标准的完全背包问题
    // 注意：表示法的硬币选取是无序的，即：1+5 5+1 看做是一种表示

    // 方法一：动态规划-时间复杂度：O(n)，空间复杂度：O(n)
    public int waysToChange(int n) {
        int[] coins = new int[] { 1, 5, 10, 25 };
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int coin : coins)
            for (int i = coin; i <= n; i++)
                dp[i] = (dp[i] + dp[i - coin]) % 1000000007;

        return dp[n];
    }

    // 方法二：数学-时间复杂度：O(n)，空间复杂度：O(1)
    // 对于给定的n，我们先枚举25分的硬币的个数i，再假设选择x个10分硬币，10分硬币可以全部用5分硬币来替代，剩下的用1分硬币补齐。
    // 25 分取 i 个的时候的方案总数，枚举 i 并累加即可得到最终的答案。
    public int waysToChange2(int n) {
        int ans = 0;
        for (int i = 0; i * 25 <= n; ++i) {
            int rest = n - i * 25;
            int a = rest / 10;
            int b = rest % 10 / 5;
            ans = (ans + (int) ((long) (a + 1) * (a + b + 1) % 1000000007)) % 1000000007;
        }
        return ans;
    }

    // 面试题 08.12. 八皇后
    // 设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。
    // 这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
    // 注意：本题相对原题做了扩展

    // 方法一：dfs 回溯（基于位运算）
    // 使用三个集合记录分别记录每一列以及两个方向的每条斜线上是否有皇后，每个集合最多包含 N 个元素
    // 因此集合的空间复杂度是 O(N)
    // 利用位运算记录皇后的信息，就可以将记录皇后信息的空间复杂度从 O(N) 降到 O(1)
    public List<List<String>> solveNQueens(int n) {
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        List<List<String>> solutions = new ArrayList<List<String>>();
        solve(solutions, queens, n, 0, 0, 0, 0);
        return solutions;
    }

    /**
     * 
     * @param solutions
     * @param queens
     * @param n
     * @param row
     * @param columns    每一位表示该列是否有棋子，0表示无棋子，1表示有棋子
     * @param diagonals1 每一位表示该对角线是否有棋子
     * @param diagonals2 每一位表示该列是否有棋子
     */
    public void solve(List<List<String>> solutions, int[] queens, int n, int row, int columns, int diagonals1,
            int diagonals2) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
            return;
        }

        int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
        while (availablePositions != 0) {
            int position = availablePositions & (-availablePositions);
            availablePositions = availablePositions & (availablePositions - 1);
            int column = Integer.bitCount(position - 1);
            queens[row] = column;
            solve(solutions, queens, n, row + 1, columns | position, (diagonals1 | position) << 1,
                    (diagonals2 | position) >> 1);
            queens[row] = -1;
        }
    }

    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }

    // 方法二：dfs 回溯（基于集合）
    // 使用三个集合 columns、diagonals1、diagonals2 分别记录每一列以及两个方向的每条斜线上是否有皇后。
    public List<List<String>> solveNQueens2(int n) {
        List<List<String>> solutions = new ArrayList<List<String>>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        Set<Integer> columns = new HashSet<Integer>();// columns = [0, n-1] 列数
        Set<Integer> diagonals1 = new HashSet<Integer>();// diagonals1 = [-n+1, n-1] 坐标之差
        Set<Integer> diagonals2 = new HashSet<Integer>();// diagonals2 = [0, 2(n-1)] 坐标之和
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }

    public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns,
            Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (columns.contains(i))
                continue;

            int diagonal1 = row - i, diagonal2 = row + i;
            if (diagonals1.contains(diagonal1) || diagonals2.contains(diagonal2))
                continue;

            queens[row] = i;
            columns.add(i);
            diagonals1.add(diagonal1);
            diagonals2.add(diagonal2);
            backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
            queens[row] = -1;
            columns.remove(i);
            diagonals1.remove(diagonal1);
            diagonals2.remove(diagonal2);
        }
    }

    // 方法二：（自己写的）dfs 回溯（基于集合）
    // 判断对角线是否有棋子的方式稍复杂
    List<Integer> ans0812 = new ArrayList<>();
    List<List<String>> res0812 = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    boolean[] usedColumns;
    int n0812;

    public List<List<String>> solveNQueens22(int n) {
        this.n0812 = n;
        this.usedColumns = new boolean[n0812];
        dfs0812(0);
        return res0812;
    }

    private void dfs0812(int row) {
        if (row == n0812) {
            List<String> temp = new ArrayList<>();
            for (int r : ans0812) {
                int columnIndex = r % n0812;
                char[] chars = new char[n0812];
                Arrays.fill(chars, '.');
                chars[columnIndex] = 'Q';
                temp.add(new String(chars));
            }
            res0812.add(temp);
        }

        for (int column = 0; column < n0812; column++) {
            if (usedColumns[column] || checkDiagonal(row, column))
                continue;
            int hash = row * n0812 + column;
            ans0812.add(hash);
            set.add(hash);
            usedColumns[column] = true;
            dfs0812(row + 1);
            ans0812.remove(ans0812.size() - 1);
            set.remove(hash);
            usedColumns[column] = false;
        }
    }

    /**
     * 检查对角线上是否有棋子
     * 
     * @param row
     * @param column
     * @return
     */
    private boolean checkDiagonal(int row, int column) {
        // 正对角线方向
        int newrow = row - 1, newcolumn = column - 1;
        while (newrow >= 0 && newcolumn >= 0) {
            if (set.contains(newrow * n0812 + newcolumn))
                return true;
            newrow--;
            newcolumn--;
        }
        newrow = row + 1;
        newcolumn = column + 1;
        while (newrow < n0812 && newcolumn < n0812) {
            if (set.contains(newrow * n0812 + +newcolumn))
                return true;
            newrow++;
            newcolumn++;
        }

        // 反对角线方向
        newrow = row + 1;
        newcolumn = column - 1;
        while (newrow < n0812 && newcolumn >= 0) {
            if (set.contains(newrow * n0812 + newcolumn))
                return true;
            newrow++;
            newcolumn--;
        }
        newrow = row - 1;
        newcolumn = column + 1;
        while (newrow >= 0 && newcolumn < n0812) {
            if (set.contains(newrow * n0812 + newcolumn))
                return true;
            newrow--;
            newcolumn++;
        }
        return false;
    }

    // 面试题 08.13. 堆箱子
    // 堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。
    // 箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。
    // 实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。
    // 输入使用数组[wi, di, hi]表示每个箱子。
    // 提示:
    // 箱子的数目不大于3000个。

    // 方法一：（自己写的）动态规划-时间复杂度：O(n^2)，空间复杂度：O(n)
    public int pileBox(int[][] box) {
        int n = box.length;
        // 必须先排序再开始遍历
        Arrays.sort(box, (box1, box2) -> {
            if (box1[0] != box2[0])
                return box1[0] - box2[0];
            else if (box1[1] != box2[1])
                return box1[1] - box2[1];
            else
                return box1[2] - box2[2];
        });

        int[] dp = new int[n];
        int res = 0;
        for (int i = 0; i < n; i++) {
            int[] cur = box[i];
            int maxUpHeight = 0;
            for (int j = 0; j < i; j++) {
                int[] up = box[j];
                // 排序后也不能保证之前的箱子一定可以放在当前箱子之上
                if (up[0] < cur[0] && up[1] < cur[1] && up[2] < cur[2])
                    maxUpHeight = Math.max(maxUpHeight, dp[j]);
            }
            dp[i] = maxUpHeight + cur[2];
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    // 面试题 08.14. 布尔运算
    // 给定一个布尔表达式和一个期望的布尔结果 result，
    // 布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。
    // 实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。
    // 提示：
    // 运算符的数量不超过 19 个

    // 方法一：（自己写的）dfs 分治 记忆化
    String s;
    int[][][] dp;

    public int countEval(String s, int result) {
        this.s = s;
        int n = s.length();
        dp = new int[n][n][];
        int[] res = dfs0814(0, n - 1);
        return result == 0 ? res[0] : res[1];
    }

    /**
     * [left, right]区间内返回false和true的组合数
     * 
     * @param left
     * @param right
     * @return [falseNum, trueNum]
     */
    private int[] dfs0814(int left, int right) {
        if (left == right)
            return s.charAt(left) == '1' ? new int[] { 0, 1 } : new int[] { 1, 0 };
        if (dp[left][right] != null)
            return dp[left][right];

        int[] ans = new int[2];
        for (int sign = left + 1; sign < right; sign = sign + 2) {
            int[] leftResult = dfs0814(left, sign - 1);
            int[] rightResult = dfs0814(sign + 1, right);
            if (s.charAt(sign) == '&') {
                ans[0] += leftResult[0] * rightResult[0];
                ans[0] += leftResult[0] * rightResult[1];
                ans[0] += leftResult[1] * rightResult[0];
                ans[1] += leftResult[1] * rightResult[1];
            } else if (s.charAt(sign) == '|') {
                ans[0] += leftResult[0] * rightResult[0];
                ans[1] += leftResult[1] * rightResult[0];
                ans[1] += leftResult[0] * rightResult[1];
                ans[1] += leftResult[1] * rightResult[1];
            } else if (s.charAt(sign) == '^') {
                ans[0] += leftResult[0] * rightResult[0];
                ans[0] += leftResult[1] * rightResult[1];
                ans[1] += leftResult[0] * rightResult[1];
                ans[1] += leftResult[1] * rightResult[0];
            }
        }
        dp[left][right] = ans;
        return ans;
    }

    // 方法二：动态规划（区间dp）-时间复杂度：O(n^2)，空间复杂度：O(n^2)
    public int countEval2(String s, int result) {
        // 特例
        if (s.length() == 0)
            return 0;
        if (s.length() == 1)
            return (s.charAt(0) - '0') == result ? 1 : 0;

        char[] ch = s.toCharArray();

        int[][][] dp = new int[ch.length][ch.length][2];// 定义状态
        // base case
        for (int i = 0; i < ch.length; i++)
            if (ch[i] == '0' || ch[i] == '1')
                dp[i][i][ch[i] - '0'] = 1;

        // 套区间dp模板（注意遍历顺序！）
        // 枚举区间长度len，跳步为2，一个数字一个符号
        for (int len = 2; len <= ch.length; len += 2) {
            // 枚举区间起点，数字位，跳步为2
            for (int i = 0; i <= ch.length - len; i += 2) {
                // 区间终点，数字位
                int j = i + len;
                // 枚举分割点，三种 '&','|', '^'，跳步为2
                for (int k = i + 1; k <= j - 1; k += 2) {
                    if (ch[k] == '&') {
                        // 结果为0 有三种情况： 0 0, 0 1, 1 0
                        // 结果为1 有一种情况： 1 1
                        dp[i][j][0] += dp[i][k - 1][0] * dp[k + 1][j][0] + dp[i][k - 1][0] * dp[k + 1][j][1]
                                + dp[i][k - 1][1] * dp[k + 1][j][0];
                        dp[i][j][1] += dp[i][k - 1][1] * dp[k + 1][j][1];
                    }
                    if (ch[k] == '|') {
                        // 结果为0 有一种情况： 0 0
                        // 结果为1 有三种情况： 0 1, 1 0, 1 1
                        dp[i][j][0] += dp[i][k - 1][0] * dp[k + 1][j][0];
                        dp[i][j][1] += dp[i][k - 1][0] * dp[k + 1][j][1] + dp[i][k - 1][1] * dp[k + 1][j][0]
                                + dp[i][k - 1][1] * dp[k + 1][j][1];
                    }
                    if (ch[k] == '^') {
                        // 结果为0 有两种情况： 0 0, 1 1
                        // 结果为1 有两种情况： 0 1, 1 0
                        dp[i][j][0] += dp[i][k - 1][0] * dp[k + 1][j][0] + dp[i][k - 1][1] * dp[k + 1][j][1];
                        dp[i][j][1] += dp[i][k - 1][1] * dp[k + 1][j][0] + dp[i][k - 1][0] * dp[k + 1][j][1];
                    }
                }
            }
        }
        return dp[0][ch.length - 1][result];
    }

    // 面试题 10.01. 合并排序的数组
    // 给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
    // 初始化 A 和 B 的元素数量分别为 m 和 n。

    // 方法一：逆向双指针-时间复杂度：O(m+n)，空间复杂度：O(1)
    // 指针设置为从后向前遍历，每次取两者之中的较大者放进 A 的最后面。
    public void merge(int[] A, int m, int[] B, int n) {
        int pa = m - 1, pb = n - 1;
        int tail = m + n - 1;
        int cur;
        while (pa >= 0 || pb >= 0) {
            if (pa == -1)
                cur = B[pb--];
            else if (pb == -1)
                cur = A[pa--];
            else if (A[pa] > B[pb])
                cur = A[pa--];
            else
                cur = B[pb--];
            A[tail--] = cur;
        }
    }

    // 方法二：双指针-时间复杂度：O(m+n)，空间复杂度：O(m+n)
    // 合并到新数组，再复制到A数组
    public void merge2(int[] A, int m, int[] B, int n) {
        int[] C = new int[n + m];
        int aindex = 0, bindex = 0, cindex = 0;
        while (aindex < m && bindex < n) {
            if (A[aindex] < B[bindex])
                C[cindex++] = A[aindex++];
            else
                C[cindex++] = B[bindex++];
        }
        while (aindex != m)
            C[cindex++] = A[aindex++];
        while (bindex != n)
            C[cindex++] = B[bindex++];

        for (int i = 0; i < m + n; i++)
            A[i] = C[i];
    }

    // 方法三：直接合并后排序-时间复杂度：O((m+n)log(m+n))，空间复杂度：O(log(m+n))

    // 面试题 10.02. 变位词组
    // 编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。
    // 注意：本题相对原题稍作修改
    // 说明：
    // 所有输入均为小写字母。
    // 不考虑答案输出的顺序。

    // 方法一：计数（出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键）
    // 时间复杂度：O(n(k+∣Σ∣))，空间复杂度：O(n(k+∣Σ∣))
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++)
                counts[str.charAt(i) - 'a']++;

            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            // 不能只用出现次数拼接， 0 10， 0 1 0 无法区分
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++)
                if (counts[i] != 0) {// 精髓所在：只拼接非0次数，尽可能减少字符键的长度！
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }

            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }

    // 方法一：（自己写的）计数（键的设计稍有不同）
    public List<List<String>> groupAnagrams11(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            String key = getKey(str);
            if (map.containsKey(key))
                map.get(key).add(str);
            else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(key, list);
            }
        }
        List<List<String>> res = new ArrayList<>();
        res.addAll(map.values());
        return res;
    }

    private String getKey(String str) {
        int[] count = new int[26];
        for (char c : str.toCharArray())
            count[c - 'a']++;

        StringBuilder res = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (count[i] == 0)
                continue;
            res.append(i).append(count[i]).append(',');
        }
        return res.toString();
    }

    // 方法二：排序（排序之后的字符串作为哈希表的键）-时间复杂度：O(nklogk)，空间复杂度：O(nk)
    public List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<>(map.values());
    }

    // 面试题 10.03. 搜索旋转数组（有重复）
    // （旋转数组类似题目：hot100. 33.搜索旋转排序数组（无重复） 剑指Offer 11.旋转数组的最小数字（有重复））
    // 搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。
    // 请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。
    // 提示:
    // arr 长度范围在[1, 1000000]之间

    // 方法一：二分查找-时间复杂度：O(logn)，空间复杂度： O(1)
    public int search(int[] arr, int target) {
        int n = arr.length;
        int left = 0, right = n - 1;
        while (left <= right) {
            // 重点1：当left符合时直接返回, 因为找的是最小的索引
            if (arr[left] == target)
                return left;
            int mid = left + (right - left) / 2;
            // 重点2：当中间值等于目标值，将右边界移到中间，因为左边可能还有相等的值
            if (arr[mid] == target)
                right = mid;
            else if (arr[0] < arr[mid]) {// 中间值处于左半边
                if (arr[0] <= target && target < arr[mid])// 目标值处于左半边，且目标值小于中间值
                    right = mid - 1;
                else
                    left = mid + 1;
            } else if (arr[0] > arr[mid]) {// 中间值处于右半边
                if (target <= arr[n - 1] && target > arr[mid])// 目标值处于右半边，且目标值大于中间值
                    left = mid + 1;
                else
                    right = mid - 1;
            } else// 中间值等于最左边数字
                  // 重点3：当中间数字与左边数字相等时，将左边界右移
                  // e.g. [1,2,1,1,1,1,1] 2 此时无法判断中间值1在左半边还是右半边
                left += 1;
        }
        return -1;
    }

    // 面试题 10.05. 稀疏数组搜索
    // 稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
    // 提示:
    // words的长度在[1, 1000000]之间

    // 方法一：（自己写的）二分查找-时间复杂度：O(logn)，空间复杂度：O(1)
    public int findString(String[] words, String s) {
        int n = words.length;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (s.equals(words[mid]))
                return mid;
            else if (s.equals(words[left]))// 一定要先判断左边界是否就是要找的目标
                return left;
            else if ("".equals(words[mid]))// 左边界左移
                left = left + 1;
            else if (compare(words[mid], s))
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }

    /**
     * 比较字符串大小
     * 
     * @param str1
     * @param str2
     * @return true str1 < str2, false str1 > str1
     */
    private boolean compare(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        for (int i = 0; i < Math.min(len1, len2); i++) {
            if (str1.charAt(i) < str2.charAt(i))
                return true;
            else if (str1.charAt(i) > str2.charAt(i))
                return false;
        }
        return len1 < len2;
    }

    // 面试题 10.09. 排序矩阵查找
    // 给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。

    // 方法一：直接查找-时间复杂度：O(mn)，空间复杂度：O(1)

    // 方法二：二分查找-时间复杂度：O(mlog(n))，空间复杂度：O(1)

    // 方法三：Z 字形查找-时间复杂度：O(m+n)，空间复杂度：O(1)
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0)
            return false;

        int m = matrix.length, n = matrix[0].length;
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target)
                return true;

            if (matrix[x][y] > target)
                --y;
            else
                ++x;
        }
        return false;
    }

    // 面试题 10.10. 数字流的秩
    // 假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：
    // 实现 track(int x) 方法，每读入一个数字都会调用该方法；
    // 实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。
    // 注意：本题相对原题稍作改动
    // 提示：
    // x <= 50000
    // track 和 getRankOfNumber 方法的调用次数均不超过 2000 次

    // 方法一：树状数组（该方法要求为正数，题目虽然只说了<= 50000，但其实都为非负数，实际操作时下标+1即可）
    // 时间复杂度：插入：O(logn)，求秩：O(logn)
    // 空间复杂度：O(n)
    class StreamRank {
        int[] tree;
        int n = 50001;

        public StreamRank() {
            tree = new int[n + 1];
        }

        int lowbit(int x) {
            return x & -x;
        }

        // 求区间[1,i]所有元素的个数
        int query(int x) {
            int ans = 0;
            for (int i = x; i > 0; i -= lowbit(i))
                ans += tree[i];
            return ans;
        }

        // 更新树
        void add(int x, int u) {
            for (int i = x; i <= n; i += lowbit(i))
                tree[i] += u;
        }

        // 题目数为非负数，可能为0，则实际+1处理
        public void track(int x) {
            add(x + 1, 1);// 这里只记录个数，不求和
        }

        // 题目数为非负数，可能为0，则实际+1处理
        public int getRankOfNumber(int x) {
            return query(x + 1);
        }
    }

    // 方法二：二分查找 + 插入排序
    // 时间复杂度：插入：O(n)，求秩：O(logn)
    // 空间复杂度：O(n)
    class StreamRank2 {
        List<Integer> nums;

        public StreamRank2() {
            nums = new ArrayList<>();
        }

        public void track(int x) {
            int index = getRankOfNumber(x); // 插入的位置刚好就是第一个大于x的下标
            nums.add(index, x);
        }

        public int getRankOfNumber(int x) { // 小于等于x的值的个数，等价于：第一个大于x的下标
            int n = nums.size();
            // 找第一个大于x的下标
            int l = 0, r = n - 1;
            while (l <= r) {
                int mid = l + r >> 1;
                if (nums.get(mid) <= x)
                    l = mid + 1;
                else if (nums.get(mid) > x)
                    r = mid - 1;
            }
            return l;
        }
    }

    // 方法三：（自己写的）基于桶（桶大小的选取在10-25效果比较好，但是怎么解释呢，跟数据集有关系吗？）
    // 时间复杂度：插入：O(n)，求秩：O(n)
    // 空间复杂度：O(n)
    class StreamRank3 {
        int interval = 20;
        int totalBuckets = 50000 / interval + 2;
        int[] count = new int[totalBuckets];
        List<List<Integer>> buckets = new ArrayList<>();

        public StreamRank3() {
            for (int i = 0; i < totalBuckets; i++)
                buckets.add(new ArrayList<>());
        }

        public void track(int x) {
            int bucketNum = 0;
            if (x >= 0)
                bucketNum = x / interval + 1;
            count[bucketNum]++;
            buckets.get(bucketNum).add(x);
        }

        public int getRankOfNumber(int x) {
            int res = 0;
            int bucketNum = x / interval + 1;
            for (int i = 0; i < bucketNum; i++)
                res += count[i];
            for (int num : buckets.get(bucketNum))
                if (num <= x)
                    res++;
            return res;
        }
    }

    // 面试题 10.11. 峰与谷
    // 在一个整数数组中，“峰”是大于或等于相邻整数的元素，相应地，“谷”是小于或等于相邻整数的元素。
    // 例如，在数组{5, 8, 4, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。
    // 现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。
    // 提示：
    // nums.length <= 10000

    // 方法一：贪心 + 位运算（交换位置）-时间复杂度：O(n)，空间复杂度：O(1)
    public void wiggleSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (i % 2 == 0) {// 下标为偶时为峰
                // 若前驱更大，则交换当前与前驱（前驱更适合做峰）
                if (nums[i] < nums[i - 1])
                    swap(nums, i, i - 1);
            } else {// 谷
                // 若前驱更小，则交换当前与前驱（前驱更适合做谷）
                if (nums[i] > nums[i - 1])
                    swap(nums, i, i - 1);
            }
        }
    }

    void swap(int[] nums, int i, int j) {
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }

    // 方法二：（自己写的）大小根堆-时间复杂度：O(nlogn)，空间复杂度：O(n)
    public void wiggleSort2(int[] nums) {
        int n = nums.length;
        PriorityQueue<Integer> min = new PriorityQueue<>((num1, num2) -> num1 - num2);
        PriorityQueue<Integer> max = new PriorityQueue<>((num1, num2) -> num2 - num1);
        for (int num : nums) {
            min.offer(num);
            max.offer(num);
        }

        for (int i = 0; i < n; i++) {
            if (i % 2 == 0)
                nums[i] = max.poll();
            else
                nums[i] = min.poll();
        }
    }

    // 面试题 16.01. 交换数字
    // 编写一个函数，不用临时变量，直接交换numbers = [a, b]中a与b的值。
    // 提示：
    // numbers.length == 2
    // -2147483647 <= numbers[i] <= 2147483647

    // 方法一：异或
    public int[] swapNumbers(int[] numbers) {
        numbers[0] ^= numbers[1];
        numbers[1] ^= numbers[0];
        numbers[0] ^= numbers[1];
        return numbers;
    }

    // 方法二：减法
    // 数据在最高位出现溢出也不会影响最终结果
    public int[] swapNumbers2(int[] numbers) {
        numbers[0] = numbers[0] - numbers[1];
        numbers[1] = numbers[0] + numbers[1];
        numbers[0] = numbers[1] - numbers[0];
        return numbers;
    }

    // 方法三：加法
    // 数据在最高位出现溢出也不会影响最终结果
    public int[] swapNumbers3(int[] numbers) {
        numbers[0] = numbers[0] + numbers[1];
        numbers[1] = numbers[0] - numbers[1];
        numbers[0] = numbers[0] - numbers[1];
        return numbers;
    }

    // 方法四：乘法（不推荐）
    public int[] swapNumbers4(int[] numbers) {
        numbers[0] = numbers[0] * numbers[1];
        numbers[1] = numbers[0] / numbers[1];
        numbers[0] = numbers[0] / numbers[1];
        return numbers;
    }

    // 面试题 16.02. 单词频率
    // 设计一个方法，找出任意指定单词在一本书中的出现频率。
    // 你的实现应该支持如下操作：
    // WordsFrequency(book)构造函数，参数为字符串数组构成的一本书
    // get(word)查询指定单词在书中出现的频率
    // 提示：
    // book[i]中只包含小写字母
    // 1 <= book.length <= 100000
    // 1 <= book[i].length <= 10
    // get函数的调用次数不会超过100000

    // 方法一：哈希表-时间复杂度：O(1)，空间复杂度：O(n)
    class WordsFrequency {
        Map<String, Integer> map = new HashMap<>();

        public WordsFrequency(String[] book) {
            for (String word : book)
                map.put(word, map.getOrDefault(word, 0) + 1);
        }

        public int get(String word) {
            return map.getOrDefault(word, 0);
        }
    }

    // 方法二：
    class Trie {
        Trie[] trie = new Trie[26];
        int count = 0;
    }

    class WordsFrequency2 {
        Trie root = new Trie();

        public WordsFrequency2(String[] book) {
            for (String word : book) {
                Trie curr = root;
                for (char c : word.toCharArray()) {
                    int index = c - 'a';
                    if (curr.trie[index] == null)
                        curr.trie[index] = new Trie();
                    curr = curr.trie[index];
                }
                curr.count++;
            }
        }

        public int get(String word) {
            Trie curr = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (curr.trie[index] == null)
                    return 0;
                curr = curr.trie[index];
            }
            return curr.count;
        }
    }

    // 面试题 16.03. 交点
    // 给定两条线段（表示为起点start = {X1, Y1}和终点end = {X2, Y2}），如果它们有交点，请计算其交点，没有交点则返回空值。
    // 要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。
    // 提示：
    // 坐标绝对值不会超过 2^7
    // 输入的坐标均是有效的二维坐标
    // 有多个交点的时候，返回以 x 为第一关键字，以 y 为第二关键字排序的最小点。

    // 方法一：参数方程（最适合用于表示线段）-时间复杂度：O(1)，空间复杂度：O(1)
    // 表示直线的方法：斜截式（斜率+截距），截距式（用两个参数分别表示在 x 轴和 y 轴上的截距）
    // 参数方程式（用三个参数分别表示直线上的一个已知点以及参数 t）
    double[] ans1603 = new double[0];

    public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
        // 线段1：x=x1+t1(x2-x1) y=y1+t1(y2-y1)
        // 线段2：x=x3+t2(x4-x3) y=y3+t2(y4-y3)
        int x1 = start1[0], y1 = start1[1];
        int x2 = end1[0], y2 = end1[1];
        int x3 = start2[0], y3 = start2[1];
        int x4 = end2[0], y4 = end2[1];

        // 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y4) 是否平行
        if ((y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3)) {// 1. 平行
            // 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上
            if ((y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1)) {
                // 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上
                if (inside(x1, y1, x2, y2, x3, y3))
                    update(x3, y3);

                // 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上
                if (inside(x1, y1, x2, y2, x4, y4))
                    update(x4, y4);

                // 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上
                if (inside(x3, y3, x4, y4, x1, y1))
                    update(x1, y1);

                // 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上
                if (inside(x3, y3, x4, y4, x2, y2))
                    update(x2, y2);
            } // else 在平行时，其余的所有情况都不会有交点
        } else {// 2. 不平行
            // 联立方程得到 t1 和 t2 的值
            double t1 = (double) (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3))
                    / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1));
            double t2 = (double) (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1))
                    / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3));
            // 判断 t1 和 t2 是否均在 [0, 1] 之间
            if (t1 >= 0.0 && t1 <= 1.0 && t2 >= 0.0 && t2 <= 1.0)
                ans1603 = new double[] { x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1) };
        }
        return ans1603;
    }

    // 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上
    // 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上
    public boolean inside(int x1, int y1, int x2, int y2, int xk, int yk) {
        // 若与 x 轴平行，只需要判断 x 的部分
        // 若与 y 轴平行，只需要判断 y 的部分
        // 若为普通线段，则都要判断
        return (x1 == x2 || (Math.min(x1, x2) <= xk && xk <= Math.max(x1, x2)))
                && (y1 == y2 || (Math.min(y1, y2) <= yk && yk <= Math.max(y1, y2)));
    }

    public void update(double xk, double yk) {
        // 将一个交点与当前 ans1603 中的结果进行比较
        // 若更优则替换
        if (ans1603.length == 0 || xk < ans1603[0] || (xk == ans1603[0] && yk < ans1603[1]))
            ans1603 = new double[] { xk, yk };
    }

    // 方法二：叉积法-时间复杂度：O(1)，空间复杂度：O(1)
    // 通过向量的基本运算来解决
    // 向量叉积的模：对于向量 a = (x1,y1) 和 b = (x2,y2)
    // 向量的叉积的模为 |c| = |axb| = |a||b|sin(a,b) = x1y2 - x2y1
    // 三角形的面积：S = |ABxAC|/2
    // 定比分点：若 P(x,y) 在线段 AB 上，端点坐标 A(x1,y2), B(x2,y2)， 且 AP 和 BP 的长度之比为 λ
    // 那么：
    // x = (x1+λx2)/(1+λ)
    // y = (y1+λy2)/(1+λ)
    // 要判断线段 AB 和 CD 是否存在交点，等价转换这个条件就是 A 和 B 位于 CD 的两侧并且 C 和 D 位于 AB 的两侧。
    // 可以连接 AC AD，如果能满足 (ABxAC)(ABxAD)<=0 ，即把AB向两个不同的方向旋转可以分别得到 AC AD，则说明 C D 位于 AB
    // 两侧
    // 若 AB CD 共线（C D 在 AB 上），则结果为0
    // 当已经确定两个线段 AB 和 CD 是相交的时候，如何求解线段的交点呢？
    // 我们可以把 AB 和 CD 看成一个四边形的两条对角线，它们相交与点 O。
    // 我们可以通过三角形面积公式求出 ABC 和 ABD 的面积，它们的比值就是 OC 和 OD 的比值，然后再用定比分点公式求出0的坐标。
    // 两三角形的作高，相似三角形

    double[] ans160302 = new double[0];

    public double[] intersection2(int[] start1, int[] end1, int[] start2, int[] end2) {
        int ax = start1[0], ay = start1[1], bx = end1[0], by = end1[1];
        int cx = start2[0], cy = start2[1], dx = end2[0], dy = end2[1];
        // 向量AC AB AD CA CB CD
        int acx = cx - ax, acy = cy - ay, abx = bx - ax, aby = by - ay, adx = dx - ax, ady = dy - ay;
        int cax = ax - cx, cay = ay - cy, cbx = bx - cx, cby = by - cy, cdx = dx - cx, cdy = dy - cy;
        // 1. 共线
        if (cross(cax, cay, cbx, cby) == 0 || cross(adx, ady, abx, aby) == 0) {
            boolean aInCd = bothSide(ax, ay, cx, cy, dx, dy), bInCd = bothSide(bx, by, cx, cy, dx, dy);
            boolean cInAb = bothSide(cx, cy, ax, ay, bx, by), dInAb = bothSide(dx, dy, ax, ay, bx, by);
            if (aInCd)
                update2(ax, ay);
            if (bInCd)
                update2(bx, by);
            if (cInAb)
                update2(cx, cy);
            if (dInAb)
                update2(dx, dy);
            return ans160302;
        }

        // 2. 平行且不共线
        if (!intersect(acx, acy, abx, aby, adx, ady, cax, cay, cbx, cby, cdx, cdy))
            return new double[0];

        // 3. 相交
        double ck = getArea(ax, ay, bx, by, cx, cy), dk = getArea(ax, ay, bx, by, dx, dy);
        double k = ck / dk;
        double rx = (cx + k * dx) / (1 + k), ry = (cy + k * dy) / (1 + k);
        return new double[] { rx, ry };
    }

    // 判断线段 (ux, uy) -- (vx, vy) 是否包含 (mx, my)
    public boolean bothSide(int mx, int my, int ux, int uy, int vx, int vy) {
        // double um = Math.sqrt((ux - mx) * (ux - mx) + (uy - my) * (uy - my));
        // double vm = Math.sqrt((vx - mx) * (vx - mx) + (vy - my) * (vy - my));
        // double uv = Math.sqrt((vx - ux) * (vx - ux) + (vy - uy) * (vy - uy));
        return (ux - mx) * (vx - mx) <= 0 && (uy - my) * (vy - my) <= 0;
    }

    // 叉积运算
    public int cross(int ux, int uy, int vx, int vy) {
        return ux * vy - vx * uy;
    }

    public void update2(double x, double y) {
        // 以 x 为第一关键字，y 为第二关键字比较两个点的大小
        // 将一个交点与当前 ans160302 中的结果进行比较
        // 若更优则替换
        if (ans160302.length == 0 || x < ans160302[0] || (x == ans160302[0] && y < ans160302[1]))
            ans160302 = new double[] { x, y };
    }

    // 判断两条线段是否有公共点
    public boolean intersect(int acx, int acy, int abx, int aby, int adx, int ady, int cax, int cay, int cbx, int cby,
            int cdx, int cdy) {
        return cross(acx, acy, abx, aby) * cross(adx, ady, abx, aby) <= 0
                && cross(cax, cay, cdx, cdy) * cross(cbx, cby, cdx, cdy) <= 0;
    }

    // 计算三角形 PQM 的面积
    public double getArea(int px, int py, int qx, int qy, int mx, int my) {
        int mpx = px - mx, mpy = py - my, mqx = qx - mx, mqy = qy - my;
        return Math.abs(0.5 * cross(mpx, mpy, mqx, mqy));
    }

    // 面试题 16.04. 井字游戏
    // 设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符" "，"X"和"O"组成，其中字符" "代表一个空位。
    // 以下是井字游戏的规则：
    // 玩家轮流将字符放入空位（" "）中。
    // 第一个玩家总是放字符"O"，且第二个玩家总是放字符"X"。
    // "X"和"O"只允许放置在空位中，不允许对已放有字符的位置进行填充。
    // 当有N个相同（且非空）的字符填充任何行、列或对角线时，游戏结束，对应该字符的玩家获胜。
    // 当所有位置非空时，也算为游戏结束。
    // 如果游戏结束，玩家不允许再放置字符。
    // 如果游戏存在获胜者，就返回该游戏的获胜者使用的字符（"X"或"O"）；
    // 如果游戏以平局结束，则返回 "Draw"；
    // 如果仍会有行动（游戏未结束），则返回 "Pending"。
    // 提示：
    // 1 <= board.length == board[i].length <= 100
    // 输入一定遵循井字棋规则

    // 方法一：（自己写的）遍历 + 求和-时间复杂度：O(n^2)，空间复杂度：O(n)
    public String tictactoe(String[] board) {
        int n = board.length;
        int[] rowsCount = new int[n];
        int[] columnsCount = new int[n];
        int[] diagonal = new int[2];
        int leftCount = 0;
        for (int i = 0; i < n; i++) {
            String row = board[i];
            for (int j = 0; j < n; j++) {
                if (row.charAt(j) == 'O') {
                    rowsCount[i]++;
                    columnsCount[j]++;
                    if (i == j)
                        diagonal[0]++;
                    if (i + j == n - 1)// 不能写成else if 可能同时满足 i == j i + j == n - 1
                        diagonal[1]++;
                } else if (row.charAt(j) == 'X') {
                    rowsCount[i]--;
                    columnsCount[j]--;
                    if (i == j)
                        diagonal[0]--;
                    if (i + j == n - 1)// 不能写成else if 可能同时满足 i == j i + j == n - 1
                        diagonal[1]--;
                } else
                    leftCount++;
            }
        }

        for (int i = 0; i < n; i++) {
            if (rowsCount[i] == n || columnsCount[i] == n)
                return "O";
            if (rowsCount[i] == -n || columnsCount[i] == -n)
                return "X";
        }

        if (diagonal[0] == n || diagonal[1] == n)
            return "O";
        if (diagonal[0] == -n || diagonal[1] == -n)
            return "X";

        return leftCount == 0 ? "Draw" : "Pending";
    }

    // 面试题 16.05. 阶乘尾数
    // 设计一个算法，算出 n 阶乘有多少个尾随零。
    // 说明: 你算法的时间复杂度应为 O(log n) 。
    // 问题分析： [1,n] 中质因子 5 的个数不会大于质因子 2 的个数
    // 方法一：计算质因子5的个数
    public int trailingZeroes(int n) {
        int ans = 0;
        while (n != 0) {
            n /= 5;
            ans += n;
        }
        return ans;
    }

    // 方法二：（自己写的，更直观）计算质因子5的个数
    public int trailingZeroes2(int n) {
        int res = 0;
        long dividend = 5;// 防越界
        while (n / dividend != 0) {
            res += n / dividend;
            dividend *= 5;
        }
        return res;
    }

    // 面试题 16.06. 最小差
    // 给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差？
    // 提示：
    // 1 <= a.length, b.length <= 100000
    // -2147483648 <= a[i], b[i] <= 2147483647
    // 正确结果在区间 [0, 2147483647] 内

    // 方法一：排序 + 双指针-时间复杂度：O(nlogn)，空间复杂度：O(n)
    public int smallestDifference(int[] a, int[] b) {
        Arrays.sort(a);
        Arrays.sort(b);
        long res = Long.MAX_VALUE;
        int aIndex = 0, bIndex = 0;
        while (aIndex < a.length && bIndex < b.length) {
            long aValue = (long) a[aIndex], bValue = (long) b[bIndex];
            res = Math.min(res, Math.abs(aValue - bValue));
            if (aValue <= bValue)
                aIndex++;
            else
                bIndex++;
        }
        return (int) res;
    }

    // 方法二：（自己写的）有序集合TreeSet + 查找临近值-时间复杂度：O(nlogn)，空间复杂度：O(n)
    public int smallestDifference2(int[] a, int[] b) {
        TreeSet<Long> treeSet = new TreeSet<>();
        for (int num : a)
            treeSet.add((long) num);

        long res = Long.MAX_VALUE;
        for (int num : b) {
            Long ceiling = treeSet.ceiling((long) num);
            Long floor = treeSet.floor((long) num);
            if (ceiling == null)
                ceiling = floor;
            if (floor == null)
                floor = ceiling;
            res = Math.min(res, Math.abs(num - ceiling));
            res = Math.min(res, Math.abs(num - floor));
        }
        return (int) res;
    }

    // 面试题 16.07. 最大数值
    // 编写一个方法，找出两个数字a和b中最大的那一个。不得使用if-else或其他比较运算符。

    // 方法一：位运算-时间复杂度：O(1)，空间复杂度：O(1)
    public int maximum(int a, int b) {
        long x = (long) a - (long) b;// 转换为long防止溢出
        int k = (int) (x >> 63);// >>有符号补位

        // 1. 当 x >= 0 的时候，k = 0, 即 a > b
        // 计算公式为 1 * a - b * 0 = a
        // 2. 当 x < 0的时候，k = -1, 即 b > a
        // 计算公式为 0 * a - b * ( -1 ) = b
        return (1 + k) * a - b * k;
    }

    // 面试题 16.08. 整数的英语表示（主站273.）
    // 给定一个整数，打印该整数的英文描述。

    // 方法一：（自己写的）模拟-时间复杂度：O(n)，空间复杂度：O(1)
    Map<Integer, String> mapx = new HashMap<>();
    {
        mapx.put(1, "One");
        mapx.put(2, "Two");
        mapx.put(3, "Three");
        mapx.put(4, "Four");
        mapx.put(5, "Five");
        mapx.put(6, "Six");
        mapx.put(7, "Seven");
        mapx.put(8, "Eight");
        mapx.put(9, "Nine");
    }
    Map<Integer, String> map1x = new HashMap<>();
    {
        map1x.put(10, "Ten");
        map1x.put(11, "Eleven");
        map1x.put(12, "Twelve");
        map1x.put(13, "Thirteen");
        map1x.put(14, "Fourteen");
        map1x.put(15, "Fifteen");
        map1x.put(16, "Sixteen");
        map1x.put(17, "Seventeen");
        map1x.put(18, "Eighteen");
        map1x.put(19, "Nineteen");
    }
    Map<Integer, String> mapx0 = new HashMap<>();
    {
        mapx0.put(20, "Twenty");
        mapx0.put(30, "Thirty");
        mapx0.put(40, "Forty");
        mapx0.put(50, "Fifty");
        mapx0.put(60, "Sixty");
        mapx0.put(70, "Seventy");
        mapx0.put(80, "Eighty");
        mapx0.put(90, "Ninety");
    }

    public String numberToWords(int num) {
        if (num == 0)
            return "Zero";
        int hundred = num % 1000;
        int thousand = num / 1000 % 1000;
        int million = num / 1000000 % 1000;
        int billion = num / 1000000000;
        String res = "";
        if (billion != 0) {
            res += numToWords(billion);
            res += " Billion ";
        }
        if (million != 0) {
            res += numToWords(million);
            res += " Million ";
        }
        if (thousand != 0) {
            res += numToWords(thousand);
            res += " Thousand ";
        }
        if (hundred != 0)
            res += numToWords(hundred);
        return res.trim();
    }

    /**
     * 1<=num<=999
     * 
     * @param num
     * @return
     */
    private String numToWords(int num) {
        int hundred = num / 100;
        int ten = num / 10 % 10;
        int one = num % 10;
        String ans = "";
        if (hundred != 0) {
            ans += mapx.get(hundred);
            ans += " Hundred ";
        }
        if (ten != 0) {
            if (ten == 1) {
                ans += map1x.get(ten * 10 + one);
                return ans.trim();
            } else
                ans += mapx0.get(ten * 10);
            ans += " ";
        }
        if (one != 0)
            ans += mapx.get(one);
        return ans.trim();
    }

    // 方法二：递归-时间复杂度：O(n)，空间复杂度：O(1)
    String[] singles = { "", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine" };
    String[] teens = { "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen",
            "Nineteen" };
    String[] tens = { "", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety" };
    String[] thousands = { "", "Thousand", "Million", "Billion" };

    public String numberToWords2(int num) {
        if (num == 0)
            return "Zero";

        StringBuffer sb = new StringBuffer();
        for (int i = 3, unit = 1000000000; i >= 0; i--, unit /= 1000) {
            int curNum = num / unit;
            if (curNum != 0) {
                num -= curNum * unit;
                StringBuffer curr = new StringBuffer();
                recursion(curr, curNum);
                curr.append(thousands[i]).append(" ");
                sb.append(curr);
            }
        }
        return sb.toString().trim();
    }

    public void recursion(StringBuffer curr, int num) {
        if (num == 0)
            return;
        else if (num < 10)
            curr.append(singles[num]).append(" ");
        else if (num < 20)
            curr.append(teens[num - 10]).append(" ");
        else if (num < 100) {// 十位
            curr.append(tens[num / 10]).append(" ");
            recursion(curr, num % 10);// 递归表示个位
        } else {// 百味
            curr.append(singles[num / 100]).append(" Hundred ");
            recursion(curr, num % 100);// 递归表示十位
        }
    }

    // 方法三：迭代
    // String[] singles = {"", "One", "Two", "Three", "Four", "Five", "Six",
    // "Seven", "Eight", "Nine"};
    // String[] teens = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen",
    // "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    // String[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty",
    // "Seventy", "Eighty", "Ninety"};
    // String[] thousands = {"", "Thousand", "Million", "Billion"};

    public String numberToWords3(int num) {
        if (num == 0)
            return "Zero";

        StringBuffer sb = new StringBuffer();
        for (int i = 3, unit = 1000000000; i >= 0; i--, unit /= 1000) {
            int curNum = num / unit;
            if (curNum != 0) {
                num -= curNum * unit;
                sb.append(toEnglish(curNum)).append(thousands[i]).append(" ");
            }
        }
        return sb.toString().trim();
    }

    public String toEnglish(int num) {
        StringBuffer curr = new StringBuffer();
        int hundred = num / 100;
        num %= 100;
        if (hundred != 0)
            curr.append(singles[hundred]).append(" Hundred ");

        int ten = num / 10;
        if (ten >= 2) {
            curr.append(tens[ten]).append(" ");
            num %= 10;
        }
        if (num > 0 && num < 10)
            curr.append(singles[num]).append(" ");
        else if (num >= 10)
            curr.append(teens[num - 10]).append(" ");

        return curr.toString();
    }

    // 面试题 16.09. 运算
    // 请实现整数数字的乘法、减法和除法运算，运算结果均为整数数字，
    // 程序中只允许使用加法运算符和逻辑运算符，允许程序中出现正负常数，不允许使用位运算。
    // 你的实现应该支持如下操作：
    // Operations() 构造函数
    // minus(a, b) 减法，返回a - b
    // multiply(a, b) 乘法，返回a * b
    // divide(a, b) 除法，返回a / b
    // 提示：
    // 你可以假设函数输入一定是有效的，例如不会出现除法分母为0的情况
    // 单个用例的函数调用次数不会超过1000次

    // 方法一：cache 数组代替位运算
    class Operations {
        // 用来获取-1（就是强行不出现-号）
        int ne = Integer.MAX_VALUE + Integer.MAX_VALUE + 1;

        int MAX_BIT = 31;// 为了替代位运算，从最高位开始比较
        // 使用long防止溢出
        long[] neCache = new long[MAX_BIT];// 放置 -1,-2,-4,-8...
        long[] poCache = new long[MAX_BIT];// 放置 1,2,4,8...
        long[] bPoCache = new long[MAX_BIT];// 存放乘数或除数的倍数，1*a,2*a,4*a,8*a...主要用于快速计算，不然容易超时
        long[] bNeCache = new long[MAX_BIT];// 存放乘数或除数的倍数 负数-1*a,-2*a,-4*a,-8*a

        // 初始化
        public Operations() {
            neCache[0] = ne;
            poCache[0] = 1;
            for (int i = 1; i < MAX_BIT; ++i) {
                neCache[i] = neCache[i + ne] + neCache[i + ne];
                poCache[i] = poCache[i + ne] + poCache[i + ne];
            }
        }

        // 计算 a - b
        // 通过 cache 数组将 b 拆分，从 a 中减去这些部分，最终即 a - b = (a - b) - (b - b)
        public int minus(int a, int b) {
            int index = MAX_BIT - 1;// 从最大值开始比较
            // 分别处理 b 正负的情况
            while (b != 0) {
                if (b > 0) {
                    if (b >= poCache[index]) { // 如果b大于2的index次方，a与b同时减
                        b += neCache[index];
                        a += neCache[index];
                    }
                } else { // b小于0时
                    if (b <= neCache[index]) {
                        b += poCache[index];
                        a += poCache[index];
                    }
                }
                index += ne;
            }
            return a;
        }

        // 计算 a * b
        // 参考快速乘，通过 cache 数组将 b 拆分，累加多个a的倍数
        public int multiply(int a, int b) {
            // 特殊情况，直接返回
            if (a == 0 || b == 0)
                return 0;
            if (a == 1)
                return b;
            if (b == 1)
                return a;
            if (a == ne)
                return minus(0, b);
            if (b == ne)
                return minus(0, a);

            int sign = (a > 0 && b > 0) || (a < 0 && b < 0) ? 1 : ne;// 最终答案的符号
            // 把b变成正数（表示有b个a相加）
            if (b < 0)
                b = minus(0, b);

            // 初始化
            bPoCache[0] = a;
            for (int i = 1; i < MAX_BIT; i++)
                bPoCache[i] = bPoCache[i + ne] + bPoCache[i + ne];

            int index = MAX_BIT - 1; // 从最高位开始比较
            int ret = 0;
            while (b > 0) {
                if (b >= poCache[index]) {
                    b += neCache[index];
                    ret += bPoCache[index];
                }
                index += ne;
            }
            // 改变返回值的符号，当前计算出的答案与最终答案符号比较
            if ((sign < 0 && ret > 0) || (sign > 0 && ret < 0))
                ret = minus(0, ret);

            return ret;
        }

        // 计算 a / b
        // 计算得到bCache，从最高位开始从a减去b的倍数
        // 由于不能使用-*/号和位运算，因此无法使用二分法
        public int divide(int a, int b) {
            // 特殊情况，直接返回
            if (a == 0)
                return 0;
            if (b == 1)
                return a;
            if (b == ne)
                return minus(0, a);
            if (a == b)
                return 1;
            if (Math.abs(a) < Math.abs(b))
                return 0;

            int ret = 0;
            int sign = (a > 0 && b > 0) || (a < 0 && b < 0) ? 1 : ne;// 最终答案的符号
            // 使用long 防止溢出
            long bPo = b;// |b|
            long bNe = b;// -|b|
            if (b < 0)
                bPo = minus(0, b);
            else
                bNe = minus(0, b);

            if (a < 0)
                a = minus(0, a);

            // 初始化
            bPoCache[0] = bPo;
            bNeCache[0] = bNe;
            for (int i = 1; i < MAX_BIT; ++i) {
                bPoCache[i] = bPoCache[i + ne] + bPoCache[i + ne];
                bNeCache[i] = bNeCache[i + ne] + bNeCache[i + ne];
            }

            int index = MAX_BIT - 1;
            while (a >= bPo) {
                if (a >= bPoCache[index]) {
                    ret += poCache[index];// 注意这里是2的index次方的值，即 bPoCache[index] = b*poCache[index]
                    a += bNeCache[index];
                }
                index += ne;
            }
            if (sign < 0)
                ret = minus(0, ret);

            return ret;
        }
    }

    // 面试题 16.10. 生存人数
    // 给定 N 个人的出生年份和死亡年份，第 i 个人的出生年份为 birth[i]，死亡年份为 death[i]，实现一个方法以计算生存人数最多的年份。
    // 你可以假设所有人都出生于 1900 年至 2000 年（含 1900 和 2000 ）之间。
    // 如果一个人在某一年的任意时期处于生存状态，那么他应该被纳入那一年的统计中。
    // 例如，生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。
    // 如果有多个年份生存人数相同且均为最大值，输出其中最小的年份。
    // 提示：
    // 0 < birth.length == death.length <= 10000
    // birth[i] <= death[i]

    // 方法一：差分数组-时间复杂度：O(n)，空间复杂度：O(m)
    // n 总人口数，m 年份数
    public int maxAliveYear(int[] birth, int[] death) {
        // 先统计每年的人口数变化
        int[] change = new int[102];
        for (int i = 0; i < birth.length; i++) {
            change[birth[i] - 1900]++;// eg:1900年出生的人导致1900年变化人数加1，存储在change[0]
            change[death[i] - 1899]--;// eg:1900年死亡的人导致1901年变化人数减1，存储在change[1]
        }
        int maxAlive = 0;
        int curAlive = 0;
        int theYear = 1900;
        // 再根据每年变化人数求一个最大值
        for (int i = 0; i < 101; i++) {
            curAlive += change[i];
            if (curAlive > maxAlive) {
                maxAlive = curAlive;
                theYear = 1900 + i;
            }
        }
        return theYear;
    }

    // 方法二：（自己写的）排序 + 优先队列-时间复杂度：O(nlogn)，空间复杂度：O(n)
    // 题目中 birth 数组并不是有序的
    public int maxAliveYear2(int[] birth, int[] death) {
        int n = birth.length;
        int[][] birthDeadth = new int[n][2];
        for (int i = 0; i < n; i++) {
            birthDeadth[i][0] = birth[i];
            birthDeadth[i][1] = death[i];
        }
        Arrays.sort(birthDeadth, (x, y) -> x[0] - y[0]);
        int ans = 0, max = 0, res = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            int curr = birthDeadth[i][0];
            while (!queue.isEmpty() && queue.peek() < curr) {
                queue.poll();
                ans--;
            }
            queue.offer(birthDeadth[i][1]);
            ans++;
            if (ans > max) {
                max = ans;
                res = curr;
            }
        }
        return res;
    }

    // 面试题 16.11. 跳水板
    // 你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。
    // 你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
    // 返回的长度需要从小到大排列。
    // 提示：
    // 0 < shorter <= longer
    // 0 <= k <= 100000

    // 方法一：模拟-时间复杂度：O(k)，空间复杂度：O(1)
    public int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0)
            return new int[] {};
        if (shorter == longer)
            return new int[] { shorter * k };

        int ans = shorter * k;
        int[] res = new int[k + 1];
        int index = 0;
        for (int i = 0; i <= k; i++) {
            res[index++] = ans;
            ans += longer - shorter;
        }

        return res;
    }

    // 面试题 16.13. 平分正方形
    // 给定两个正方形及一个二维平面。请找出将这两个正方形分割成两半的一条直线。假设正方形顶边和底边与 x 轴平行。
    // 每个正方形的数据square包含3个数值：
    // 正方形的左下顶点坐标[X,Y] = [square[0],square[1]]，以及正方形的边长square[2]。
    // 所求直线穿过两个正方形会形成4个交点，请返回4个交点形成线段的两端点坐标（两个端点即为4个交点中距离最远的2个点，
    // 这2个点所连成的线段一定会穿过另外2个交点）。
    // 2个端点坐标[X1,Y1]和[X2,Y2]的返回格式为{X1,Y1,X2,Y2}，
    // 要求若X1 != X2，需保证X1 < X2，否则需保证Y1 <= Y2。
    // 若同时有多条直线满足要求，则选择斜率最大的一条计算并返回（与Y轴平行的直线视为斜率无穷大）。
    // 提示：
    // square.length == 3
    // square[2] > 0

    // 方法一：斜截式表示直线（通过斜率判断相交于正方形的哪条边）-时间复杂度：O(1)，空间复杂度：O(1)
    public double[] cutSquares(int[] square1, int[] square2) {
        // 第一个正方形的中心点，x,y坐标及正方形边长
        double x1 = square1[0] + square1[2] / 2.0;
        double y1 = square1[1] + square1[2] / 2.0;
        int d1 = square1[2];
        // 第二个正方形的中心点，x,y坐标及正方形边长
        double x2 = square2[0] + square2[2] / 2.0;
        double y2 = square2[1] + square2[2] / 2.0;
        int d2 = square2[2];
        // 结果集
        double[] res = new double[4];
        // 两个中心坐标在同一条x轴上，此时直线的斜率无穷大
        if (x1 == x2) {
            res[0] = x1;
            res[1] = Math.min(square1[1], square2[1]);
            res[2] = x1;
            res[3] = Math.max(square1[1] + d1, square2[1] + d2);
        } else {
            // 斜率存在，则计算斜率和系数，y = kx + b;
            double k = (y1 - y2) / (x1 - x2);// 斜率计算公式
            double b = y1 - k * x1;

            // 斜率绝对值大于1，说明与正方形的上边和下边相交
            if (Math.abs(k) > 1) {
                // 先计算底边，也就是两个正方形左下坐标y的最小值
                res[1] = Math.min(square1[1], square2[1]);
                res[0] = (res[1] - b) / k;
                // 再计算顶边，也就是两个正方形左下坐标y+边长的最大值
                res[3] = Math.max(square1[1] + d1, square2[1] + d2);
                res[2] = (res[3] - b) / k;
            } else {// 斜率绝对值小于等于1，说明与正方形的左边和右边相交，同理
                // 先计算底边，也就是两个正方形左下坐标x的最小值
                res[0] = Math.min(square1[0], square2[0]);
                res[1] = res[0] * k + b;
                // 再计算顶边，也就是两个正方形左下坐标x+边长的最大值
                res[2] = Math.max(square1[0] + d1, square2[0] + d2);
                res[3] = res[2] * k + b;
            }
        }
        // 题目要求x1 < x2,如果结果不满足，我们交换两个点的坐标即可
        if (res[0] > res[2]) {
            swap(res, 0, 2);
            swap(res, 1, 3);
        }
        return res;
    }

    public void swap(double[] res, int x, int y) {
        double temp = res[x];
        res[x] = res[y];
        res[y] = temp;
    }

    // 面试题 16.14. 最佳直线
    // 给定一个二维平面及平面上的 N 个点列表Points，其中第i个点的坐标为Points[i]=[Xi,Yi]。
    // 请找出一条直线，其通过的点的数目最多。
    // 设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S，你仅需返回[S[0],S[1]]作为答案，
    // 若有多条直线穿过了相同数量的点，则选择S[0]值较小的直线返回，S[0]相同则选择S[1]值较小的直线返回。
    // 提示：
    // 2 <= len(Points) <= 300
    // len(Points[i]) = 2

    // 方法一：向量表示直线（暴力枚举）-时间复杂度：O(n^3)，空间复杂度：O(1)
    // 以已知直线上的点作为基准求向量
    public int[] bestLine(int[][] points) {
        int[] res = new int[2];// 用来存满足条件的两个点
        int num = 0;// 记录直线穿过点的数量
        int maxNum = 0; // 记录num的最大值
        int len = points.length;

        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                if (len - 1 - j + 2 <= maxNum)
                    break;// 就算后面所有点都在该直线上也无法超过maxNum，提前剪枝

                num = 2;// 先确定 i, j 两个点
                // i, j 两个点的向量（x1,y1）
                long x1 = points[j][0] - points[i][0];
                long y1 = points[j][1] - points[i][1];
                for (int k = j + 1; k < len; k++) {
                    // 第三个点与第一个点构成的向量（x2,y2）
                    long x2 = points[k][0] - points[i][0];
                    long y2 = points[k][1] - points[i][1];
                    if (x1 * y2 == x2 * y1)// 满足向量共线的条件，且 i 为公共顶点，故在一条直线上
                        num++;
                }
                // 更新最优解
                if (num > maxNum) {
                    maxNum = num;
                    res[0] = i;
                    res[1] = j;
                }
            }
        }
        return res;
    }

    // 方法二：直线的一般式方程（哈希表）-时间复杂度：O(n^2)，空间复杂度：O(n)
    // 实际耗时比方法一的O(n^3)还长，可能是因为数据量还不够大，时间复杂度体现不够明显。可能是因为两次最大公约数计算耗时，O(logm)
    // 直线的一般式方程:Ax + By + C = 0。
    // 直线一般式方程适用于所有的二维空间直线。
    // 而其他直线方程，如点斜式、两点式，要么不能支持所有情况下的直线（比如跟坐标轴垂直或者平行），
    // 要么不能支持所有情况下的点（比如x坐标相等，或者y坐标相等）。
    // 所以一般式方程在用计算机处理二维图形数据时特别有用。
    // 注意：
    // 1）这里，要唯一定位一条直线。只需要知道三个数A、B、C即可。
    // 不过，由于4x + 6y + 2 = 0、2x + 3y + 1 = 0其实是表示同一条直线。所以，要对A、B、C求最大公约数。
    // 2）对于任意两点(X1,Y1)、(X2,Y2)，都有 A = Y2 - Y1, B = X1 - X2, C = X2Y1 - X1Y2
    public int[] bestLine2(int[][] points) {
        int max = 0;
        Long maxHash = 0L;
        int[] res = new int[2];
        Map<Long, Integer> map = new HashMap<>();// 直线：其上点数
        Map<Long, int[]> record = new HashMap<>();// 直线：确定该直线的下标最小的两个点的下标
        for (int i = 0; i < points.length - 1; i++) {
            for (int j = i + 1; j < points.length; j++) {
                // 计算ABC
                long A = points[j][1] - points[i][1];
                long B = points[i][0] - points[j][0];
                long C = ((long) points[j][0]) * points[i][1] - ((long) points[i][0]) * points[j][1];
                // 求ABC三个数的最大公约数，并归一化
                long gcd = gcd(gcd(A, B), C);
                A /= gcd;
                B /= gcd;
                C /= gcd;
                long hash = A * 1313131 + B * 13131 + C;// 根据ABC计算表示该直线的键值
                // 更新 map record
                int count = map.getOrDefault(hash, 1) + 1;
                map.put(hash, count);
                if (count == 2)// 根据 i, j 得到的直线是一条全新的直线，初始化
                    record.put(hash, new int[] { i, j });// 此时 i, j 是该直线的下标最小的两个点的下标
                if (count > max) {// 更新最终答案res，此时直线上点数更多
                    max = count;
                    maxHash = hash;
                    res = record.get(hash);
                } else if (count == max) {// 更新最终答案res，此时直线上点数相同，但是可能初始两点下标更小
                    int[] t1 = record.get(maxHash);
                    int[] t2 = record.get(hash);
                    if (t1[0] > t2[0] || t1[0] == t2[0] && t1[1] > t2[1]) {
                        maxHash = hash;
                        res = t2;
                    }
                }
            }
        }
        return res;
    }

    // 求最大公约数
    private long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    // 面试题 16.15. 珠玑妙算
    // 珠玑妙算游戏（the game of master mind）的玩法如下。
    // 计算机有4个槽，每个槽放一个球，颜色可能是红色（R）、黄色（Y）、绿色（G）或蓝色（B）。
    // 例如，计算机可能有RGGB 4种（槽1为红色，槽2、3为绿色，槽4为蓝色）。作为用户，你试图猜出颜色组合。
    // 打个比方，你可能会猜YRGB。要是猜对某个槽的颜色，则算一次“猜中”；要是只猜对颜色但槽位猜错了，则算一次“伪猜中”。
    // 注意，“猜中”不能算入“伪猜中”。
    // 给定一种颜色组合solution和一个猜测guess，
    // 编写一个方法，返回猜中和伪猜中的次数answer，其中answer[0]为猜中的次数，answer[1]为伪猜中的次数。
    // 提示：
    // len(solution) = len(guess) = 4
    // solution和guess仅包含"R","G","B","Y"这4种字符

    // 方法一：一次遍历-时间复杂度：O(n)，空间复杂度：O(1)
    // 字符在solution中出现计+1，在guess中出现计-1
    public int[] masterMind(String solution, String guess) {
        int fake = 0, real = 0;
        int[] map = new int[26];
        for (int i = 0; i < 4; i++) {
            char sol = solution.charAt(i), gue = guess.charAt(i);
            if (sol == gue)// 计猜中一次
                real++;
            else {
                // 这两步判断不会重复计次
                if (map[sol - 'A'] < 0)// 之前在guess中出现并记录，则计伪猜中一次
                    fake++;
                map[sol - 'A']++;
                if (map[gue - 'A'] > 0)// 之前在solution中出现并记录，则计伪猜中一次
                    fake++;
                map[gue - 'A']--;
            }
        }
        int[] ans = { real, fake };
        return ans;
    }

    // 方法二：（自己写的）两次遍历-时间复杂度：O(n)，空间复杂度：O(1)
    public int[] masterMind2(String solution, String guess) {
        Map<Character, Integer> solutionMap = new HashMap<>();
        Map<Character, Integer> guessMap = new HashMap<>();
        int ans0 = 0, ans1 = 0;
        for (int i = 0; i < 4; i++) {
            char solutionCharacter = solution.charAt(i);
            char guessCharater = guess.charAt(i);
            if (solutionCharacter == guessCharater)
                ans0++;
            else {
                solutionMap.put(solutionCharacter, solutionMap.getOrDefault(solutionCharacter, 0) + 1);
                guessMap.put(guessCharater, guessMap.getOrDefault(guessCharater, 0) + 1);
            }
        }

        for (char c : guessMap.keySet())
            if (solutionMap.containsKey(c))
                ans1 += Math.min(solutionMap.get(c), guessMap.get(c));
        return new int[] { ans0, ans1 };
    }

    // 面试题 16.16. 部分排序
    // 给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。
    // 注意：n-m尽量最小，也就是说，找出符合条件的最短序列。
    // 函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。
    // 提示：
    // 0 <= len(array) <= 1000000

    // 方法一：记录最大最小值（一次遍历）-时间复杂度：O(n)，空间复杂度：O(1)
    public int[] subSort(int[] array) {
        if (array == null || array.length == 0)
            return new int[] { -1, -1 };
        int last = -1, first = -1;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int len = array.length;
        for (int i = 0; i < len; i++) {
            if (array[i] < max)
                last = i;
            else
                max = Math.max(max, array[i]);
            if (array[len - 1 - i] > min)
                first = len - 1 - i;
            else
                min = Math.min(min, array[len - 1 - i]);
        }
        return new int[] { first, last };
    }

    // 方法二：记录最大最小值（两次遍历）-时间复杂度：O(n)，空间复杂度：O(1)
    public int[] subSort2(int[] array) {
        int n = array.length;
        int right = -1, max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int cur = array[i];
            if (cur < max)
                right = i;
            else
                max = Math.max(max, cur);
        }
        int left = -1, min = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            int cur = array[i];
            if (cur > min)
                left = i;
            else
                min = Math.min(min, cur);
        }
        return new int[] { left, right };
    }

    // 方法三：单调栈（两次遍历）-时间复杂度：O(n)，空间复杂度：O(n)
    // 频繁而不必要的入栈出栈操作还是很浪费时间的

    // 方法四：排序-时间复杂度：O(nlogn)，空间复杂度：O(n)

    // 面试题 16.17. 连续数列（hot100 53.）
    // 给定一个整数数组，找出总和最大的连续数列，并返回总和。
    // 进阶：
    // 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

    // 方法一：动态规划-时间复杂度：O(n)，空间复杂度：O(1)
    // 动态规划转移方程：f(i) = max{f(i−1)+nums[i], nums[i]}
    // 思想：与前者狼狈为奸，或者是自立门户
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

    // 方法二：分治（线段树）-时间复杂度：O(n)，空间复杂度：O(logn)
    // 取 m = (l+r)/2，对区间 [l,m] 和 [m+1,r] 分治求解
    // 对于一个区间 [l,r]，我们可以维护四个量：
    // lSum 表示 [l,r] 内以 l 为左端点的最大子段和
    // rSum 表示 [l,r] 内以 r 为右端点的最大子段和
    // iSum 表示 [l,r] 的区间和
    // mSum 表示 [l,r] 内的最大子段和
    // 考虑 [l,r] 的 mSum 对应的区间是否跨越 m

    // 方法二的意义：
    // 线段树不仅可以解决区间 [0, n-1]，还可以用于解决任意的子区间 [l,r] 的问题。
    // 如果我们把 [0, n-1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，
    // 即建成一颗真正的树之后，我们就可以在 O(logn) 的时间内求到任意区间内的答案，
    // 我们甚至可以修改序列中的值，做一些简单的维护，之后仍然可以在 O(logn) 的时间内求到任意区间内的答案，
    // 对于大规模查询的情况下，这种方法的优势便体现了出来。

    public class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public int maxSubArray2(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r)// 分到只剩一个数
            return new Status(a[l], a[l], a[l], a[l]);

        int m = (l + r) >> 1;
        // 分为左右区间
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    // 合并
    public Status pushUp(Status l, Status r) {
        // iSum 表示 [l,r] 的区间和
        int iSum = l.iSum + r.iSum;

        // lSum 表示 [l,r] 内以 l 为左端点的最大子段和
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);

        // rSum 表示 [l,r] 内以 r 为右端点的最大子段和
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);

        // mSum 表示 [l,r] 内的最大子段和（左：不横跨，右：横跨）
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }

    // 面试题 16.18. 模式匹配
    // 你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。
    // 例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。
    // 但需注意"a"和"b"不能同时表示相同的字符串。
    // 编写一个方法判断value字符串是否匹配pattern字符串。
    // 提示：
    // 1 <= len(pattern) <= 1000
    // 0 <= len(value) <= 1000
    // 你可以假设pattern只包含字母"a"和"b"，value仅包含小写字母。

    // 方法一：枚举
    // 在分配字符串之前，我们不妨先分配a和b对应字符串的长度。
    // 如果确定了长度，那么我们只要将value 按照pattern中出现字母的顺序，划分成lp个子串，
    // 并判断其中a对应的子串是否相同，以及b对应的子串是否相同即可。
    // 具体地，假设pattern中出现了ca个a以及lp-ca个b，并且a和b对应字符串的长度分别为la和lb，那么必须要满足:
    // ca*la + (lp-ca)*lb = lv

    // 在枚举了长度之后，我们就可以根据 pattern 来将 value 划分成lp个子串。
    // 具体地，我们遍历pattern，并用一个指针pos来帮助我们进行划分。
    // 当我们遍历到一个a时，我们取出从pos开始，长度为la的子串。
    // 如果这是我们第一次遇到字母a，我们就得到了a应该对应的子串;
    // 否则，我们将取出的子串与a应该对应的子串进行比较，如果不相同，说明模式匹配失败。
    // 同理，当我们遍历到一个b时，我们取出从pos开始，长度为lb的子串，根据是否第一次遇到字母 b来进行比较。
    // 在比较结束后，我们将pos向后移动，进行下一个字母的匹配。
    // 在遍历完成之后，如果匹配没有失败，我们还需要判断一下a和b是否对应了不同的子串。
    // 只有它们对应的子串不同时，才是一种满足题目要求的模式匹配。
    public boolean patternMatching(String pattern, String value) {
        // 1. 保证 pattern 中 a 出现的次数不少于 b 出现的次数。如果不满足，我们就将 a 和 b 互相替换；
        int count_a = 0, count_b = 0;
        for (char ch : pattern.toCharArray()) {
            if (ch == 'a')
                ++count_a;
            else
                ++count_b;
        }
        if (count_a < count_b) {
            int temp = count_a;
            count_a = count_b;
            count_b = temp;
            char[] array = pattern.toCharArray();
            for (int i = 0; i < array.length; i++)
                array[i] = array[i] == 'a' ? 'b' : 'a';

            pattern = new String(array);
        }

        // 2. 如果 value 为空，那么要求pattern也为空(lp=0)或者只出现了字母a (lp-ca=0)，这两种情况均等同于lp-ca=0。
        // 在其余情况下，都无法匹配成功;
        if (value.length() == 0)
            return count_b == 0;

        // 3. 如果pattern为空且 value 不为空，那么无法匹配成功;
        if (pattern.length() == 0)
            return false;

        // 4. 如果pattern和value均非空,我们就可以枚举 la 并使用上面提到的算法进行判断。
        // 枚举 la
        for (int len_a = 0; count_a * len_a <= value.length(); ++len_a) {
            int rest = value.length() - count_a * len_a;// value 除去 a 的剩余字符数
            // 4.1. count_b == 0 && rest == 0
            // b 出现次数为0，且剩余字符数为0
            // 4.2. count_b != 0 && rest % count_b == 0
            // b 出现次数不为0，且能剩余字符数能被 b 除尽
            if ((count_b == 0 && rest == 0) || (count_b != 0 && rest % count_b == 0)) {
                // 与之对应的 lb
                int len_b = (count_b == 0 ? 0 : rest / count_b);
                int pos = 0;// 记录当前匹配开始的下标位置
                boolean correct = true;// 标记是否正确匹配
                String value_a = "", value_b = "";
                // 开始按照 pattern 匹配
                for (char ch : pattern.toCharArray()) {
                    if (ch == 'a') {
                        String sub = value.substring(pos, pos + len_a);
                        if (value_a.length() == 0)// 第一次匹配a时赋值，后续都跟这个比较
                            value_a = sub;
                        else if (!value_a.equals(sub)) {// 匹配失败，提前退出循环
                            correct = false;
                            break;
                        }
                        pos += len_a;
                    } else {// 'b'
                        String sub = value.substring(pos, pos + len_b);
                        if (value_b.length() == 0)// 第一次匹配b时赋值，后续都跟这个比较
                            value_b = sub;
                        else if (!value_b.equals(sub)) {// 匹配失败，提前退出循环
                            correct = false;
                            break;
                        }
                        pos += len_b;
                    }
                }
                if (correct && !value_a.equals(value_b))
                    return true;
            }
        }
        return false;
    }

    // 面试题 16.19. 水域大小
    // 你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。
    // 若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。
    // 池塘的大小是指相连接的水域的个数。
    // 编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
    // 提示：
    // 0 < len(land) <= 1000
    // 0 < len(land[i]) <= 1000

    // 方法一：dfs
    int[][] land;
    int m1619, n1619;
    boolean[][] visited1619;

    public int[] pondSizes(int[][] land) {
        this.land = land;
        this.m1619 = land.length;
        this.n1619 = land[0].length;
        this.visited1619 = new boolean[m1619][n1619];
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < m1619; i++)
            for (int j = 0; j < n1619; j++)
                if (land[i][j] == 0 && !visited1619[i][j])
                    list.add(dfs1619(i, j));

        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++)
            res[i] = list.get(i);

        Arrays.sort(res);
        return res;
    }

    private int dfs1619(int i, int j) {
        visited1619[i][j] = true;
        int ans = 1;
        for (int iDelta = -1; iDelta <= 1; iDelta++) {
            for (int jDelta = -1; jDelta <= 1; jDelta++) {
                int newi = i + iDelta;
                int newj = j + jDelta;
                if (0 <= newi && newi < m1619 && 0 <= newj && newj < n1619 && land[newi][newj] == 0
                        && !visited1619[newi][newj])
                    ans += dfs1619(newi, newj);
            }
        }
        return ans;
    }

    // 方法二：bfs

    // 面试题 16.20. T9键盘
    // 在老式手机上，用户通过数字键盘输入，手机将提供与这些数字相匹配的单词列表。每个数字映射到0至4个字母。
    // 给定一个数字序列，实现一个算法来返回匹配单词的列表。你会得到一张含有有效单词的列表。映射如下图所示：
    // 提示：
    // num.length <= 1000
    // words.length <= 500
    // words[i].length == num.length
    // num中不会出现 0, 1 这两个数字

    // 方法一：数字序列匹配单词→单词匹配数字序列-时间复杂度：O(mn)，空间复杂度：O(1)
    // 数字序列长度 n = 单词长度 n，单词个数 m
    public List<String> getValidT9Words(String num, String[] words) {
        int[] map = new int[] { 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9 };
        int n = num.length();
        int[] nums = new int[n];

        // 为减少计算，提前把num字符串转换成int数组
        for (int i = 0; i < n; i++)
            nums[i] = num.charAt(i) - '0';

        List<String> res = new ArrayList<>();
        for (String word : words)
            if (isValid(nums, word, map))
                res.add(word);
        return res;
    }

    // 根据映射判断单词是否合法
    private boolean isValid(int[] nums, String word, int[] map) {
        for (int i = 0; i < nums.length; i++)
            if (map[word.charAt(i) - 'a'] != nums[i])
                return false;
        return true;
    }

    // 方法二：（自己写的）字典树-时间复杂度：O(mn)，空间复杂度：O(n)
    // 这道题用前缀树有点大材小用了...
    Map<Integer, List<Character>> map1620 = new HashMap<>();
    {
        map1620.put(2, new ArrayList<>(Arrays.asList('a', 'b', 'c')));
        map1620.put(3, new ArrayList<>(Arrays.asList('d', 'e', 'f')));
        map1620.put(4, new ArrayList<>(Arrays.asList('g', 'h', 'i')));
        map1620.put(5, new ArrayList<>(Arrays.asList('j', 'k', 'l')));
        map1620.put(6, new ArrayList<>(Arrays.asList('m', 'n', 'o')));
        map1620.put(7, new ArrayList<>(Arrays.asList('p', 'q', 'r', 's')));
        map1620.put(8, new ArrayList<>(Arrays.asList('t', 'u', 'v')));
        map1620.put(9, new ArrayList<>(Arrays.asList('w', 'x', 'y', 'z')));
    }

    class Trie1620 {
        Trie1620[] vals = new Trie1620[26];
        boolean isEnd = false;
    }

    StringBuilder ans1620 = new StringBuilder();
    List<String> res1620 = new ArrayList<>();

    public List<String> getValidT9Words2(String num, String[] words) {
        Trie1620 root = new Trie1620();
        for (String word : words) {
            Trie1620 curr = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (curr.vals[index] == null)
                    curr.vals[index] = new Trie1620();
                curr = curr.vals[index];
            }
            curr.isEnd = true;
        }

        dfs(0, num, root);
        return res1620;
    }

    private void dfs(int index, String num, Trie1620 root) {
        if (index == num.length() && root.isEnd) {
            res1620.add(new String(ans1620));
            return;
        }
        for (char c : map1620.get(num.charAt(index) - '0')) {
            if (root.vals[c - 'a'] != null) {
                ans1620.append(c);
                dfs(index + 1, num, root.vals[c - 'a']);
                ans1620.deleteCharAt(index);
            }
        }
    }

    // 面试题 16.21. 交换和
    // 给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。
    // 返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。
    // 提示：
    // 1 <= array1.length, array2.length <= 100000

    // 方法一：（自己写的）哈希表-时间复杂度：O(n)，空间复杂度：O(n)
    public int[] findSwapValues(int[] array1, int[] array2) {
        Set<Integer> set1 = new HashSet<>(), set2 = new HashSet<>();
        int sum1 = 0, sum2 = 0;
        for (int num : array1) {
            set1.add(num);
            sum1 += num;
        }
        for (int num : array2) {
            set2.add(num);
            sum2 += num;
        }

        if ((sum1 - sum2) % 2 != 0)// 负奇数%2==1
            return new int[] {};

        int diff = (sum1 - sum2) / 2;
        for (int num : set2)
            if (set1.contains(num + diff))
                return new int[] { num + diff, num };

        return new int[] {};
    }

    // 面试题 16.22. 兰顿蚂蚁
    // 一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。每行走一步，蚂蚁执行以下操作。
    // (1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。
    // (2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位。
    // 编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。
    // 网格由数组表示，每个元素是一个字符串，代表网格中的一行，黑色方格由 'X' 表示，白色方格由 '_' 表示，
    // 蚂蚁所在的位置由 'L', 'U', 'R', 'D' 表示，分别表示蚂蚁 左、上、右、下 的朝向。
    // 只需要返回能够包含蚂蚁走过的所有方格的最小矩形。
    // 说明：
    // K <= 100000
    // 方法一：集合存储坐标-时间复杂度：O(k)，空间复杂度：O(1)
    // 不使用数组、ArrayList存储无限网格，而使用集合存储
    private class Position {
        // 横坐标 x 纵坐标 y
        int x, y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == this)
                return true;
            if (!(obj instanceof Position))
                return false;
            Position o = (Position) obj;
            return x == o.x && y == o.y;
        }

        // 改写哈希算法，使两个 Position 对象可以比较坐标而不是内存地址
        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }

    public List<String> printKMoves(int K) {
        char[] direction = { 'L', 'U', 'R', 'D' };
        // 用“向量”(x, y)记录方向，顺序与上一行方向的字符顺序保持一致
        // 当前元素的后一个元素可以通过顺时针旋转90°得到；同理，当前元素的前一个元素可以通过逆时针旋转90°得到
        int[][] offset = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
        Position antPos = new Position(0, 0);// 蚂蚁的起始位置
        int antDir = 2;// 蚂蚁起始方向的向量序号

        Set<Position> blackSet = new HashSet<>();// 用集合存储所有黑块的坐标，网格默认全白，仅记录黑块坐标即可恢复路径
        while (K > 0) {
            Position t = new Position(antPos.x, antPos.y);// 新的坐标对象，记录当前蚂蚁坐标
            if (blackSet.add(t))// 如果黑块集合能存入，说明脚下的块不在集合中，也就意味着是白色，方向序号循环自增1
                antDir = (antDir + 1) % 4;
            else {// 否则说明脚下的块已经在集合中，也就意味着是黑色，方向序号循环自增3，相当于自减1，-1 % 4 == -1 不行
                antDir = (antDir + 3) % 4;
                blackSet.remove(t);// 删除黑块坐标，即将黑块变白
            }
            // 蚂蚁移动位置（根据朝向向前移动一格）
            antPos.x += offset[antDir][0];
            antPos.y += offset[antDir][1];
            K--;
        }

        // 计算边界，即包含蚂蚁走过的所有方格的最小矩形，最终输出的网格的行数和列数
        int left = antPos.x, top = antPos.y, right = antPos.x, bottom = antPos.y;
        for (Position pos : blackSet) {
            left = Math.min(left, pos.x);
            top = Math.min(top, pos.y);
            right = Math.max(right, pos.x);// 坐标正方向
            bottom = Math.max(bottom, pos.y);// 坐标正方向
        }

        // 生成路径
        char[][] grid = new char[bottom - top + 1][right - left + 1];
        for (char[] row : grid)// 填充白块
            Arrays.fill(row, '_');
        for (Position pos : blackSet)// 替换黑块
            grid[pos.y - top][pos.x - left] = 'X';
        grid[antPos.y - top][antPos.x - left] = direction[antDir];// 替换蚂蚁（最终朝向）

        // 利用网格生成字符串列表
        List<String> result = new ArrayList<>();
        for (char[] row : grid)
            result.add(String.valueOf(row));
        return result;
    }

    // 面试题 16.24. 数对和
    // 设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。
    // 提示：
    // nums.length <= 100000

    // 方法一：（自己写的）哈希表-时间复杂度：O(n)，空间复杂度：O(n)
    public List<List<Integer>> pairSums(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        List<List<Integer>> res = new ArrayList<>();
        for (int num : nums) {
            int leftNum = target - num;
            if (map.getOrDefault(leftNum, 0) > 0) {
                res.add(Arrays.asList(leftNum, num));// （一般还要放入实现类的构造器中，asList返回的是内部类）
                map.put(leftNum, map.get(leftNum) - 1);
            } else
                map.put(num, map.getOrDefault(num, 0) + 1);
        }
        return res;
    }

    // 方法二：排序 + 双指针-时间复杂度：O(nlogn)，空间复杂度：O(1)
    public List<List<Integer>> pairSums2(int[] nums, int target) {
        Arrays.sort(nums);// 对数组进行排序
        List<List<Integer>> ans = new LinkedList<>();
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];// 两个指针所指的两个元素和
            if (sum < target)// 如果两个的和小于目标值，那么left指针向右走一步继续寻找
                ++left;
            else if (sum > target)// 如果两个的和大于目标值，那么right指针向左走一步继续寻找
                --right;
            else// 如果刚好等于要找的target值，那么加入结果集中，并且left指针和right指针分别向右和向左走一步(因为一个数只能属于一个数对)
                ans.add(Arrays.asList(nums[left++], nums[right--]));
        }
        return ans;
    }

    // 面试题 16.25. LRU 缓存（hot100 146.）
    // 设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。
    // 缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。
    // 它应该支持以下操作： 获取数据 get 和 写入数据 put 。
    // 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
    // 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。
    // 当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

    // 方法一：（自己写的）双向链表 + 哈希表-时间复杂度：O(1)，空间复杂度：O(capacity)
    class LRUCache {
        class LinkedNode {
            LinkedNode prev;
            LinkedNode next;
            int key;
            int value;
        }

        int capacity;
        LinkedNode dummyHead = new LinkedNode();
        LinkedNode dummyTail = new LinkedNode();
        Map<Integer, LinkedNode> map = new HashMap<>();

        public LRUCache(int capacity) {
            this.capacity = capacity;
            dummyHead.next = dummyTail;
            dummyTail.prev = dummyHead;
        }

        public int get(int key) {
            if (map.containsKey(key)) {
                LinkedNode node = map.get(key);
                deleteNode(node);
                offerNode(node);
                return node.value;
            } else
                return -1;
        }

        public void put(int key, int value) {
            if (get(key) != -1) {
                map.get(key).value = value;
                return;
            }

            if (map.size() == capacity) {
                LinkedNode deleteNode = dummyHead.next;
                deleteNode(deleteNode);
                map.remove(deleteNode.key);
            }
            LinkedNode node = new LinkedNode();
            node.key = key;
            node.value = value;
            offerNode(node);
            map.put(key, node);
        }

        private void offerNode(LinkedNode node) {
            node.prev = dummyTail.prev;
            node.next = dummyTail;
            dummyTail.prev.next = node;
            dummyTail.prev = node;
        }

        private void deleteNode(LinkedNode node) {
            node.next.prev = node.prev;
            node.prev.next = node.next;
        }
    }

    // 方法二：自己写的lowb，用java自带的LinkedHashMap-时间复杂度：O(1)，空间复杂度：O(capacity)

    // 面试题 16.26. 计算器
    // 给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。
    // 表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格  。 整数除法仅保留整数部分。
    // 说明：
    // 你可以假设所给定的表达式都是有效的。
    // 请不要使用内置的库函数 eval。

    // 方法一：栈-时间复杂度：O(n)，空间复杂度：O(n)
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        char preSign = '+';
        int num = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (Character.isDigit(s.charAt(i)))// 数字
                num = num * 10 + s.charAt(i) - '0';
            // 非数字且非空格 或者是 最后一个空格 e.g." 1+ 32 "
            if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {
                switch (preSign) {
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);// 方便后续求和
                        break;
                    case '*':
                        stack.push(stack.pop() * num);
                        break;
                    default:
                        stack.push(stack.pop() / num);
                }
                preSign = s.charAt(i);// 数字num前的符号
                num = 0;// 在这里置0
            }
        }
        int ans = 0;
        while (!stack.isEmpty())
            ans += stack.pop();
        return ans;
    }

    // 方法二：（自己写的）双端队列-时间复杂度：O(n)，空间复杂度：O(n)
    public int calculate2(String s) {
        // 1. 预处理，将s分解成：数字、符号
        List<String> list = new ArrayList<>();
        int index = 0;
        while (index < s.length()) {
            if (Character.isDigit(s.charAt(index))) {
                int num = 0;
                while (index < s.length() && Character.isDigit(s.charAt(index))) {
                    // Integer.valueOf(Char);//Char转int 是 转换成对应ASCII码，不同于作差取值 char - '0'
                    num = num * 10 + s.charAt(index) - '0';
                    index++;
                }
                list.add(String.valueOf(num));
            } else if (s.charAt(index) == ' ')
                index++;
            else {
                list.add(String.valueOf(s.charAt(index)));
                index++;
            }
        }

        // 2. 处理 * / 运算
        Deque<String> dq = new ArrayDeque<>();
        for (int i = 0; i < list.size(); i++) {
            String string = list.get(i);
            if ("*".equals(string) || "/".equals(string)) {
                int num1 = Integer.valueOf(dq.pollLast());
                int num2 = Integer.valueOf(list.get(i + 1));
                if ("*".equals(string))
                    dq.offerLast(String.valueOf(num1 * num2));
                else if ("/".equals(string))
                    dq.offerLast(String.valueOf(num1 / num2));
                i++;
            } else
                dq.offerLast(string);
        }

        // 3. 处理 + - 运算
        int res = Integer.valueOf(dq.pollFirst());
        while (!dq.isEmpty()) {
            String sign = dq.pollFirst();
            int num = Integer.valueOf(dq.pollFirst());
            if ("+".equals(sign))
                res += num;
            else if ("-".equals(sign))
                res -= num;
        }
        return res;
    }

    // 面试题 17.01. 不用加号的加法（剑指Offer 65.）

    // 设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。
    // 提示：
    // a, b 均可能是负数或 0
    // 结果不会溢出 32 位整数

    // 方法一：位运算-时间复杂度：O(1)，空间复杂度：O(1)
    public int add(int a, int b) {
        // 第一次与b作和后，后续都是与进位作和
        while (b != 0) {// 当进位全为 0 时跳出
            int carry = (a & b) << 1;// carry = 进位 11 = 1 01 01 = 10
            a = a ^ b;// a = 非进位和 00 11 = 0， 01 10 = 1
            b = carry;// b = 进位
        }
        return a;
    }

    // 方法二：（自己写的，模拟进位）位运算-时间复杂度：O(1)，空间复杂度：O(1)
    public int add2(int a, int b) {
        int adder = 0, res = 0;
        for (int i = 0; i < 32; i++) {
            int mask = 1 << i;
            if ((a & mask) != 0 && (b & mask) != 0) {// 该位都为1
                if (adder == 1)
                    res = res | mask;
                else
                    adder = 1;
            } else if ((a & mask) == 0 && (b & mask) == 0) {// 该位都为0
                if (adder == 1) {
                    res = res | mask;
                    adder = 0;
                }
            } else {// 该位只有一个为1
                if (adder == 0)
                    res = res | mask;
            }
        }
        return res;
    }

    // 面试题 17.04. 消失的数字
    // 数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
    // 注意：本题相对书上原题稍作改动

    // 方法一：数学-时间复杂度：O(n)，空间复杂度：O(1)
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int total = n * (n + 1) / 2;
        int arrSum = 0;
        for (int i = 0; i < n; i++)
            arrSum += nums[i];
        return total - arrSum;
    }

    // 方法二：（自己写的）原地记录 + 遍历-时间复杂度：O(n)，空间复杂度：O(1)
    public int missingNumber2(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int nextIndex = nums[i];
            if (nextIndex < 0)// 还原
                nextIndex += n + 1;
            if (nextIndex == n)// 超出下标范围，直接跳过不记录
                continue;
            nums[nextIndex] -= n + 1;
        }

        for (int i = 0; i < n; i++)
            if (nums[i] >= 0)
                return i;

        return n;// 遍历完数组都没有找到未记录过的数，则缺失的数字一定是不记录的n
    }

    // 方法三：位运算-时间复杂度：O(n)，空间复杂度：O(1)
    // a^a = 0，a^0 = a
    public int missingNumber3(int[] nums) {
        int xor = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) // 数组中的n-1个数
            xor ^= nums[i];
        for (int i = 0; i <= n; i++) // 本来应该出现的n个数
            xor ^= i;
        return xor;// 2n-1个数中只出现了一次的数，即为数组中缺失的数
    }

    // 方法四：哈希-时间复杂度：O(n)，空间复杂度：O(n)
    public int missingNumber4(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int n = nums.length;
        for (int i = 0; i < n; i++)
            set.add(nums[i]);

        int missing = -1;
        for (int i = 0; i <= n; i++)
            if (!set.contains(i)) {
                missing = i;
                break;
            }
        return missing;
    }

    // 面试题 17.05. 字母与数字
    // 给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
    // 返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。
    // 提示：
    // array.length <= 100000

    // 方法一：（自己写的）前缀和-时间复杂度：O(n)，空间复杂度：O(1)
    public String[] findLongestSubarray(String[] array) {
        int n = array.length;
        int[] mem = new int[2 * n];// 记录array中前缀和i的最小下标，[-n+1, n-1]映射到[1, 2n-1]
        Arrays.fill(mem, Integer.MIN_VALUE);// 初始值，表示还未记录
        mem[n] = -1;// 前缀和0出现在下标-1

        int preSum = 0;
        int maxLength = 0, leftMinIndex = 0;
        for (int i = 0; i < n; i++) {
            preSum += Character.isDigit(array[i].charAt(0)) ? 1 : -1;
            if (mem[preSum + n] == Integer.MIN_VALUE)// 未曾见过该前缀和（即mem数组中没有记录）
                mem[preSum + n] = i;// 记录该前缀和的下标
            else {// 见过该前缀和（即mem数组中已有记录）
                int leftIndex = mem[preSum + n];
                int curLength = i - leftIndex + 1;
                if (curLength > maxLength) {
                    maxLength = curLength;
                    leftMinIndex = leftIndex;
                }
            }
        }
        if (maxLength == 0)// 不存在符合题意要求的子数组
            return new String[] {};
        else
            return Arrays.copyOfRange(array, leftMinIndex + 1, leftMinIndex + maxLength);
    }

    // 面试题 17.06. 2出现的次数（剑指Offer 43.）
    // 编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。
    // 提示：
    // n <= 10^9

    // 方法一：（自己写的）分别统计各位上的2的个数-时间复杂度：O(logn)，空间复杂度：O(1)
    public int numberOf2sInRange(int n) {
        int res = 0;
        int oneZeros = 1;
        // 依次统计个、十、百位...上2的个数
        while (n >= oneZeros) {
            // 统计完整区间内2的个数，个位（x0-x9）、十位（x00-x99）、百位（x000-x999）...
            res += n / (oneZeros * 10) * oneZeros;
            // 统计非完整区间内2的个数，个位（x0-x?）、十位（x00-x??）、百位（x000-x???）...
            int left = n % (oneZeros * 10);// 提取对应个位（0-?）、十位（00-??）、百位（000-???）...
            res += Math.min(oneZeros, Math.max(0, left - 2 * oneZeros + 1));// 2的个数在[0, oneZeros]之间
            oneZeros *= 10;
        }
        return res;
    }

    // 面试题 17.07. 婴儿名字
    // 每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。
    // 有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。
    // 给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。
    // 设计一个算法打印出每个真实名字的实际频率。
    // 注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。
    // 在结果列表中，选择 字典序最小 的名字作为真实名字。
    // 提示：
    // names.length <= 100000

    // 方法一：（自己写的）并查集（合并时稍特殊）-时间复杂度：O(n)，空间复杂度：O(n)
    // 一般并查集合并：对于一对节点，子节点祖先指向父节点祖先
    // 该题：对于一对节点，无需比较两节点大小，直接比较两节点祖先的大小，排序靠后的祖先节点指向排序较前的祖先节点
    int[] fathers;

    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        // 1. 预处理
        // 将 synonyms 中出现的名字标号，建立映射：名字→下标，下标→名字
        Map<String, Integer> nameIndex = new HashMap<>();
        Map<Integer, String> indexName = new HashMap<>();

        int nameNums = 0;
        for (String synonym : synonyms) {
            String[] synonymNames = synonym.substring(1, synonym.length() - 1).split(",");
            if (!nameIndex.containsKey(synonymNames[0])) {
                nameIndex.put(synonymNames[0], nameNums);
                indexName.put(nameNums, synonymNames[0]);
                nameNums++;
            }
            if (!nameIndex.containsKey(synonymNames[1])) {
                nameIndex.put(synonymNames[1], nameNums);
                indexName.put(nameNums, synonymNames[1]);
                nameNums++;
            }
        }

        // 初始化父亲数组，每个节点默认指向自己
        this.fathers = new int[nameNums];
        for (int i = 0; i < nameNums; i++)
            fathers[i] = i;

        // 2. 合并
        for (String synonym : synonyms) {
            String[] synonymNames = synonym.substring(1, synonym.length() - 1).split(",");
            int s0Index = nameIndex.get(synonymNames[0]), s1Index = nameIndex.get(synonymNames[1]);
            int s0FatherIndex = getFather(s0Index), s1FatherIndex = getFather(s1Index);
            if (indexName.get(s0FatherIndex).compareTo(indexName.get(s1FatherIndex)) > 0)
                fathers[s0FatherIndex] = s1FatherIndex;
            else
                fathers[s1FatherIndex] = s0FatherIndex;
        }

        // 3. 根据并查集计数
        Map<String, Integer> nameCount = new HashMap<>();
        for (String name : names) {
            String[] arr = name.substring(0, name.length() - 1).split("\\(");
            String originalName = arr[0], fatherName = arr[0];
            int count = Integer.valueOf(arr[1]);
            // 没有出现在并查集中，则说明该名字没有别名
            if (nameIndex.containsKey(originalName))
                fatherName = indexName.get(getFather(nameIndex.get(originalName)));
            nameCount.put(fatherName, nameCount.getOrDefault(fatherName, 0) + count);
        }

        // 4. 构造最终答案
        String[] res = new String[nameCount.size()];
        int index = 0;
        for (String name : nameCount.keySet())
            res[index++] = name + "(" + nameCount.get(name) + ")";

        return res;
    }

    // 递归查找祖先节点，路径压缩
    private int getFather(int cur) {
        if (fathers[cur] == cur)
            return cur;
        int father = getFather(fathers[cur]);
        fathers[cur] = father;
        return father;
    }

    // 面试题 17.08. 马戏团人塔（类比：最长递增子序列）
    // 有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。
    // 出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。
    // 已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
    // 提示：
    // height.length == weight.length <= 10000
    // 题目隐藏信息：矮一点且轻一点，是严格<，所以在自定义排序时，身高升序，体重降序

    // 方法一：（自己写的）排序 + 二分查找-时间复杂度：O(nlogn)，空间复杂度：O(n)
    // dp 数组，下标：序列长度，值：在这个序列长度下，最后一人的最小体重
    public int bestSeqAtIndex(int[] height, int[] weight) {
        int n = height.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++)
            arr[i] = new int[] { height[i], weight[i] };
        Arrays.sort(arr, (arr1, arr2) -> {
            if (arr1[0] != arr2[0])
                return arr1[0] - arr2[0];
            else
                return arr2[1] - arr1[1];
        });

        int res = 1;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            int currHeight = arr[i][1];
            int index = Arrays.binarySearch(dp, currHeight);
            if (index >= 0)
                continue;
            // index 小于0，二分查找未找到该数，转换得到应当插入的位置，即需要更新dp数组的位置
            index = -index - 1;
            res = Math.max(res, index);
            dp[index] = Math.min(dp[index], currHeight);// 在这个序列长度下，最后一人的最小体重
        }
        return res;
    }

    // 方法二：（自己写的）排序 + 动态规划（超时）-时间复杂度：O(n^2)，空间复杂度：O(n)
    // dp 数组，下标：排序后的第几个人，值：当这个人为最后一人时最多叠几个人
    public int bestSeqAtIndex2(int[] height, int[] weight) {
        int n = height.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++)
            arr[i] = new int[] { height[i], weight[i] };
        Arrays.sort(arr, (arr1, arr2) -> {
            if (arr1[0] != arr2[0])
                return arr1[0] - arr2[0];
            else
                return arr2[1] - arr1[1];
        });

        int[] dp = new int[n];
        dp[0] = 1;
        int res = 1;
        for (int i = 1; i < n; i++) {
            int maxLength = 1;
            for (int j = 0; j < i; j++)
                if (arr[j][1] < arr[i][1])
                    maxLength = Math.max(maxLength, dp[j] + 1);
            dp[i] = maxLength;
            res = Math.max(res, maxLength);
        }
        return res;
    }

    // 面试题 17.09. 第 k 个数（剑指Offer 49.）

    // 方法一：动态规划-时间复杂度：O(k)，空间复杂度：O(k)
    public int getKthMagicNumber(int k) {
        int[] dp = new int[k + 1];
        dp[1] = 1;
        int p3 = 1, p5 = 1, p7 = 1;
        for (int i = 2; i <= k; i++) {
            int num3 = dp[p3] * 3, num5 = dp[p5] * 5, num7 = dp[p7] * 7;
            dp[i] = Math.min(Math.min(num3, num5), num7);
            if (dp[i] == num3)
                p3++;
            if (dp[i] == num5)
                p5++;
            if (dp[i] == num7)
                p7++;
        }
        return dp[k];
    }

    // 方法二：（自己写的）最小堆-时间复杂度：O(klogk)，空间复杂度：O(k)
    public int getKthMagicNumber2(int k) {
        PriorityQueue<Long> pq = new PriorityQueue<>();
        long cur = 0L;
        pq.offer(1L);
        while (k != 0) {
            while (cur == pq.peek())
                pq.poll();
            cur = pq.poll();
            pq.offer(cur * 3);
            pq.offer(cur * 5);
            pq.offer(cur * 7);
            k--;
        }
        return (int) cur;
    }
    // 面试题 17.10. 主要元素（hot100 169.）
    // 数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。
    // 请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
    // 改题相较于原题的不同之处在于：可能不存在多数元素，即需要两次遍历确认，e.g. 3,2,1 3,2,3

    // 方法一：（自己写的）Boyer-Moore 投票算法-时间复杂度：O(n)，空间复杂度：O(1)
    public int majorityElement(int[] nums) {
        int res = -1, count = 0;
        for (int num : nums) {
            if (count == 0) {
                count++;
                res = num;
            } else {
                if (res == num)
                    count++;
                else
                    count--;
            }
        }
        if (count == 0)// 一定不存在多数元素
            return -1;
        if (count > 1)// 一定存在多数元素
            return res;

        int n = nums.length, resCount = 0;
        for (int num : nums)
            if (num == res)
                resCount++;

        if (resCount > n / 2)
            return res;
        else
            return -1;
    }

    // 面试题 17.11. 单词距离
    // 有个内含单词的超大文本文件，给定任意两个不同的单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。
    // 如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?
    // 提示：
    // words.length <= 100000
    // 审题：这里的单词距离是相隔单词数，而不是通过是否相邻计算跳数

    // 方法一：一次遍历-时间复杂度：O(n)，空间复杂度：O(1)
    public int findClosest(String[] words, String word1, String word2) {
        int length = words.length;
        int ans = length;
        int index1 = -1, index2 = -1;
        for (int i = 0; i < length; i++) {
            String word = words[i];
            if (word.equals(word1))
                index1 = i;
            else if (word.equals(word2))
                index2 = i;

            if (index1 >= 0 && index2 >= 0)
                ans = Math.min(ans, Math.abs(index1 - index2));
        }
        return ans;
    }

    // 方法一：（重复查找优化）哈希记录单词出现位置-时间复杂度：O(n)，空间复杂度：O(1)
    Map<String, List<Integer>> wordPositions = new HashMap<>();

    public int findClosest11(String[] words, String word1, String word2) {
        // 预处理
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (!wordPositions.containsKey(word))
                wordPositions.put(word, new ArrayList<>());
            wordPositions.get(word).add(i);
        }

        List<Integer> word1IndexList = wordPositions.get(word1);
        List<Integer> word2IndexList = wordPositions.get(word2);

        int i = 0, j = 0;
        int res = Integer.MAX_VALUE;
        while (i < word1IndexList.size() && j < word2IndexList.size()) {
            int word1Position = word1IndexList.get(i);
            int word2Position = word2IndexList.get(j);
            res = Math.min(res, Math.abs(word1Position - word2Position));
            if (word1Position < word2Position)
                i++;
            else
                j++;
        }
        return res;

    }

    // 面试题 17.12. BiNode
    // 二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。
    // 实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。
    // 返回转换后的单向链表的头节点。
    // 注意：本题相对原题稍作改动
    // 提示：
    // 节点数量不会超过 100000。

    // 方法一：（自己写的）dfs-时间复杂度：O(n)，空间复杂度：O(n)
    TreeNode dummyHead = new TreeNode(-1);
    TreeNode prev1712 = dummyHead;

    public TreeNode convertBiNode(TreeNode root) {
        dfs1712(root);
        prev1712.left = null;
        prev1712.right = null;
        return dummyHead.right;
    }

    private void dfs1712(TreeNode root) {
        if (root == null)
            return;
        dfs1712(root.left);
        prev1712.left = null;
        prev1712.right = root;
        prev1712 = root;
        dfs1712(root.right);
    }

    // 面试题 17.13. 恢复空格
    // 哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。
    // 像句子"I reset the computer. It still didn’t boot!"
    // 已经变成了"iresetthecomputeritstilldidntboot"。
    // 在处理标点符号和大小写之前，你得先把它断成词语。
    // 当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。
    // 假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。
    // 注意：本题相对原题稍作改动，只需返回未识别的字符数
    // 提示：
    // 0 <= len(sentence) <= 1000
    // dictionary中总字符数不超过 150000。
    // 你可以认为dictionary和sentence中只包含小写字母。
    // 要求：要求未识别的字符数最少

    // 方法一：字典树 + 动态规划-时间复杂度：O(n^2)，空间复杂度：O(n)
    class Solution1713 {
        class Trie {
            public Trie[] next;
            public boolean isEnd;

            public Trie() {
                next = new Trie[26];
                isEnd = false;
            }

            public void insert(String s) {
                Trie curPos = this;
                for (int i = s.length() - 1; i >= 0; --i) {
                    int t = s.charAt(i) - 'a';
                    if (curPos.next[t] == null)
                        curPos.next[t] = new Trie();
                    curPos = curPos.next[t];
                }
                curPos.isEnd = true;
            }
        }

        public int respace(String[] dictionary, String sentence) {
            // 1. 建树（按照字符串逆序）
            int n = sentence.length();
            Trie root = new Trie();
            for (String word : dictionary)
                root.insert(word);

            // 2.3. 动态规划 + 搜索前缀树
            int[] dp = new int[n + 1];// 表示字符串[0, i]在最优断句时，最少的未识别的字符数
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;
            for (int i = 1; i <= n; ++i) {// 选择结束字符的位置
                dp[i] = dp[i - 1] + 1;

                Trie curPos = root;
                for (int j = i; j >= 1; --j) {// 断句位置j
                    int t = sentence.charAt(j - 1) - 'a';
                    if (curPos.next[t] == null) // 提前返回，已经不可能从[0, i]中找到断句位置
                        break;
                    else if (curPos.next[t].isEnd)
                        dp[i] = Math.min(dp[i], dp[j - 1]);
                    if (dp[i] == 0) // 已无法找到更优断句，提前返回
                        break;
                    curPos = curPos.next[t];
                }
            }
            return dp[n];
        }
    }

    // 方法一：（自己写的）字典树 + 动态规划-时间复杂度：O(n^2)，空间复杂度：O(n)
    // 逻辑更清晰，但是效率稍差标答
    class Solution1713_11 {
        class Trie {
            Trie[] vals = new Trie[26];
            boolean isEnd;
        }

        public int respace(String[] dictionary, String sentence) {
            int n = sentence.length();
            if (n == 0)
                return 0;
            // 1. 建树（按照字符串正序）
            Trie root = new Trie();
            for (String word : dictionary) {
                Trie curr = root;
                for (char c : word.toCharArray()) {
                    int index = c - 'a';
                    if (curr.vals[index] == null)
                        curr.vals[index] = new Trie();
                    curr = curr.vals[index];
                }
                curr.isEnd = true;
            }

            // 2. 搜索树，dp 数组赋初值
            int[][] dp = new int[n][n];
            // dp 数组默认值：左右间距内的字符数，即全都是未识别的字符
            for (int i = 0; i < n; i++)
                for (int j = i; j < n; j++)
                    dp[i][j] = j - i + 1;
            // 搜索字典树，标记出现在字符串中的单词
            for (int i = 0; i < n; i++) {// 以字符串i开始从头遍历字典树
                Trie curr = root;
                for (int charIndex = i; charIndex < n; charIndex++) {
                    int currIndex = sentence.charAt(charIndex) - 'a';
                    if (curr.vals[currIndex] == null)// 提前返回
                        break;
                    curr = curr.vals[currIndex];
                    if (curr.isEnd)
                        dp[i][charIndex] = 0;// 置0表示区间内无未识别的字符
                }
            }

            // 3. 动态规划
            for (int j = 1; j < n; j++)// 选择结束字符的位置
                for (int i = 0; i < j; i++)// 选择中间点位置进行拼接
                    dp[0][j] = Math.min(dp[0][j], dp[0][i] + dp[i + 1][j]);

            return dp[0][n - 1];
        }
    }

    // 方法二：字符串哈希-时间复杂度：O(n^2)，空间复杂度：O(n)
    // 使用 Rabin-Karp 方法 替换字典树
    // 使用字典树的目的是查找某一个串 s 是否在一个串的集合 S 当中，
    // 并且当我们知道 s 是否在 S 中之后，可以快速的知道在 s 后添加某一个新的字母得到的新串 s 是否在 S 中，这个转移的过程是 O(1) 的。
    // 这是我们采用字典树而放弃使用哈希表的一个理由。

    // Rabin-Karp 方法 65ms 逼近字典树的 9ms 20ms
    // 直接使用 Set<String> 654ms

    // Rabin-Karp 字符串编码是一种将字符串映射成整数的编码方式，可以看成是一种哈希算法。
    // 具体地，假设字符串包含的字符种类不超过∣Σ∣（其中 Σ 表示字符集），
    // 那么我们选一个大于等于 ∣Σ∣ 的整数 base，就可以将字符串看成 base 进制的整数，将其转换成十进制数后，就得到了字符串对应的编码。
    // 例如给定字符串 s = abca，其包含的字符种类为 3（即 abc 三种）。
    // 我们取 base = 9，将字符串 s 看成九进制数 9(0120) ，转换为十进制为 9999，也就是说字符串 abca 的编码为 9999。
    // 一般地，计算编码值的公式见 getHash 方法
    // 这样做的好处是什么？我们可以发现一个结论：
    // 两个字符串 s 和 t 相等，当且仅当它们的长度相等且编码值相等。
    // 对于长度为 k 的所有字符串，我们会将它们编码成位数为 k（包含前导零）的 base 进制数，这是一个单射，因此结论成立。
    // 这样以来，我们就可以通过比较两个字符串的编码值判断它们是否相等了。
    // 但聪明的读者有没有发现什么问题呢？
    // 当字符串的长度很长时，对应的编码值也会很大，这样可能就无法用一般语言中的整数类型（例如 int，long long 等）存储编码值了。
    // 对此，一般的解决方法是将编码值对一个数 mod 进行取模，使得其保持在整数类型的范围之内。

    static final long P = Integer.MAX_VALUE;
    static final long BASE = 41;

    public int respace(String[] dictionary, String sentence) {
        Set<Long> hashValues = new HashSet<Long>();
        int n = sentence.length();
        for (String word : dictionary)
            hashValues.add(getHash(word));

        int[] f = new int[n + 1];
        Arrays.fill(f, n);

        f[0] = 0;
        for (int i = 1; i <= n; ++i) {
            f[i] = f[i - 1] + 1;
            long hashValue = 0;
            for (int j = i; j >= 1; --j) {
                int t = sentence.charAt(j - 1) - 'a' + 1;
                hashValue = (hashValue * BASE + t) % P;// 根据 s 的哈希值快速获得新串的哈希值
                if (hashValues.contains(hashValue))
                    f[i] = Math.min(f[i], f[j - 1]);
            }
        }
        return f[n];
    }

    public long getHash(String s) {
        long hashValue = 0;
        for (int i = s.length() - 1; i >= 0; --i)
            hashValue = (hashValue * BASE + s.charAt(i) - 'a' + 1) % P;
        return hashValue;
    }

    // 面试题 17.14. 最小K个数（剑指Offer 40.）
    // 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

    // 方法一：排序-时间复杂度：O(nlogn)，空间复杂度：O(logn)

    // 方法二：堆（优先队列）-时间复杂度：O((n-k)logk)，空间复杂度：O(logk)

    // 方法二：基于数组的堆的实现（215.hot100有）

    // 方法三：快排思想（快速选择）-时间复杂度：O(n)，具体证明可以参考《算法导论》第 9 章第 2 小节，空间复杂度：O(logn)

    // 面试题 17.15. 最长单词
    // 给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。
    // 若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。
    // 提示：
    // 0 <= len(words) <= 200
    // 1 <= len(words[i]) <= 100
    // 时间复杂度要求很苛刻，主要还是考察dfs
    // 使用字典树优化会超时，建树需要太长时间了，本身数据集不是很大没必要

    // 方法一：（自己写的）哈希 + dfs
    class Solution1714 {
        Set<String> set = new HashSet<>();

        public String longestWord(String[] words) {
            Arrays.sort(words, (word1, word2) -> word2.length() - word1.length());// 排序，先找长单词
            for (String word : words)
                set.add(word);

            String res = "";
            for (String word : words) {
                if (word.length() < res.length())// 不可能出现更优解了，直接返回
                    return res;
                if (!set.contains(word))// 重复单词，之前dfs过，已经remove
                    continue;
                set.remove(word);// 先remove再dfs，防止自己组成自己
                if (dfs(word)) {
                    // 更新res
                    if (word.length() > res.length())
                        res = word;
                    else if (word.length() == res.length())
                        res = res.compareTo(word) < 0 ? res : word;
                }
            }
            return res;
        }

        private boolean dfs(String word) {
            for (int i = 1; i < word.length(); i++) {
                String subword1 = word.substring(0, i);
                String subword2 = word.substring(i, word.length());
                boolean containsSubword1 = set.contains(subword1);
                boolean containsSubword2 = set.contains(subword2);
                if (containsSubword1 && containsSubword2)
                    return true;
                else if (containsSubword1)
                    if (dfs(subword2))
                        return true;
            }
            return false;
        }
    }

    // 面试题 17.16. 按摩师
    // 一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。
    // 在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。
    // 给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
    // 注意：本题相对原题稍作改动

    // 方法一：（自己写的）动态规划-时间复杂度：O(n)，空间复杂度：O(1)
    public int massage(int[] nums) {
        int n = nums.length;
        if (n == 0)
            return 0;
        int dp0 = 0;
        int dp1 = nums[0];
        for (int i = 1; i < n; i++) {
            int newdp0 = Math.max(dp0, dp1);
            int newdp1 = dp0 + nums[i];
            dp0 = newdp0;
            dp1 = newdp1;
        }
        return Math.max(dp0, dp1);
    }

    // 面试题 17.17. 多次搜索
    // 给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。
    // 输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。
    // 提示：
    // 0 <= len(big) <= 1000
    // 0 <= len(smalls[i]) <= 1000
    // smalls的总字符数不会超过 100000。
    // 你可以认为smalls中没有重复字符串。
    // 所有出现的字符均为英文小写字母。

    // 方法一：前缀树-时间复杂度：O(mn)，空间复杂度：O(mk)，n：big长度，m：smalls个数，k：smalls中最长字符串的长度
    // 1. trie中记录smalls中的字符串，末尾记录字符串，方便后面遍历。
    // 2. trie中的search用于搜索字符串，将搜索到的字符串存入返回值中。
    // 3. 遍历big长字符串，将其与trie匹配。
    // 4. 按smalls顺序输出最终结果。
    class Solution1717 {
        class Trie {
            TrieNode root;

            public Trie(String[] words) {
                root = new TrieNode();
                for (String word : words) {
                    TrieNode node = root;
                    for (char w : word.toCharArray()) {
                        int i = w - 'a';
                        if (node.next[i] == null)
                            node.next[i] = new TrieNode();
                        node = node.next[i];
                    }
                    node.end = word;
                }
            }

            public List<String> search(String str) {
                TrieNode node = root;
                List<String> res = new ArrayList<>();
                for (char c : str.toCharArray()) {
                    int i = c - 'a';
                    if (node.next[i] == null)
                        break;
                    node = node.next[i];
                    if (node.end != null)
                        res.add(node.end);
                }
                return res;
            }
        }

        class TrieNode {
            String end;
            TrieNode[] next = new TrieNode[26];
        }

        public int[][] multiSearch(String big, String[] smalls) {
            Trie trie = new Trie(smalls);
            Map<String, List<Integer>> hit = new HashMap<>();
            for (int i = 0; i < big.length(); i++) {
                List<String> matchs = trie.search(big.substring(i));
                for (String word : matchs) {
                    if (!hit.containsKey(word))
                        hit.put(word, new ArrayList<>());
                    hit.get(word).add(i);
                }
            }

            int[][] res = new int[smalls.length][];
            for (int i = 0; i < smalls.length; i++) {
                List<Integer> list = hit.get(smalls[i]);
                if (list == null) {
                    res[i] = new int[0];
                    continue;
                }
                int size = list.size();
                res[i] = new int[size];
                for (int j = 0; j < size; j++)
                    res[i][j] = list.get(j);
            }
            return res;
        }

    }

    // 方法二：（自己写的）java api-时间复杂度：O(n^2)，空间复杂度：O(1)
    public int[][] multiSearch(String big, String[] smalls) {
        int n = smalls.length;
        int[][] res = new int[n][];

        for (int i = 0; i < n; i++) {
            String small = smalls[i];
            List<Integer> list = new ArrayList<>();
            int j = 0, index = 0;
            while (j < big.length() && !"".equals(small)) {
                index = big.indexOf(small, j);
                if (index == -1)
                    break;
                list.add(index);
                j = index + 1;
            }
            int[] ans = new int[list.size()];
            for (int ansIndex = 0; ansIndex < list.size(); ansIndex++)
                ans[ansIndex] = list.get(ansIndex);
            res[i] = ans;
        }

        return res;
    }

    // 面试题 17.18. 最短超串
    // 假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。
    // 返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。
    // 提示：
    // big.length <= 100000
    // 1 <= small.length <= 100000

    // 方法一：（自己写的）滑动窗口
    public int[] shortestSeq(int[] big, int[] small) {
        int n = big.length;
        int left = 0, right = n - 1;
        int[] res = new int[] { 0, n - 1 };
        Map<Integer, Integer> numCount = new HashMap<>();
        Map<Integer, Integer> window = new HashMap<>();
        int count = 0;

        for (int num : small)
            numCount.put(num, numCount.getOrDefault(num, 0) + 1);

        for (right = 0; right < n; right++) {
            int add = big[right];
            if (!numCount.containsKey(add))
                continue;

            window.put(add, window.getOrDefault(add, 0) + 1);
            if (numCount.get(add) == window.get(add))
                count++;

            if (count < numCount.size())
                continue;

            for (; left < right; left++) {
                int remove = big[left];
                if (!window.containsKey(remove))
                    continue;
                if (numCount.get(remove) == window.get(remove))
                    break;
                window.put(remove, window.get(remove) - 1);
            }
            if (right - left < res[1] - res[0]) {
                res[0] = left;
                res[1] = right;
            }
        }
        return count == numCount.size() ? res : new int[] {};
    }

    // 面试题 17.19. 消失的两个数字
    // 给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
    // 以任意顺序返回这两个数字均可。
    // 提示：
    // nums.length <= 30000

    // 方法一：（自己写的）位运算-时间复杂度：O(n)，空间复杂度：O(1)
    public int[] missingTwo(int[] nums) {
        int[] res = new int[2];
        int n = nums.length;

        int xor = 0;
        for (int i = 1; i <= n + 2; i++)
            xor ^= i;
        for (int num : nums)
            xor ^= num;
        int bit = 0;
        int mask = 1;
        for (; bit < 31; bit++) {
            mask = 1 << bit;
            if ((xor & mask) != 0)
                break;
        }

        int xor1 = 0;
        for (int i = 1; i <= n + 2; i++)
            if ((i & mask) != 0)
                xor1 ^= i;

        for (int num : nums)
            if ((num & mask) != 0)
                xor1 ^= num;

        res[0] = xor1;
        res[1] = xor ^ xor1;
        return res;
    }

    // 面试题 17.20. 连续中值
    // 随机产生数字并传递给一个方法。你能否完成这个方法，在每次产生新值时，寻找当前所有值的中间值（中位数）并保存。
    // 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
    // 例如，
    // [2,3,4] 的中位数是 3
    // [2,3] 的中位数是 (2 + 3) / 2 = 2.5
    // 设计一个支持以下两种操作的数据结构：
    // void addNum(int num) - 从数据流中添加一个整数到数据结构中。
    // double findMedian() - 返回目前所有元素的中位数。
    // 示例：
    // addNum(1)
    // addNum(2)
    // findMedian() -> 1.5
    // addNum(3)
    // findMedian() -> 2

    // 方法一：（自己写的）两个优先队列-时间复杂度：O(logn)，空间复杂度：O(1)
    class MedianFinder {
        PriorityQueue<Integer> lowerHalf;
        PriorityQueue<Integer> higherHalf;

        public MedianFinder() {
            lowerHalf = new PriorityQueue<>((x, y) -> y - x);
            higherHalf = new PriorityQueue<>((x, y) -> x - y);
        }

        public void addNum(int num) {
            // lowerHalf.size()==0, higherHalf.size()==0
            if (lowerHalf.isEmpty()) {
                lowerHalf.offer(num);
                return;
            }
            // lowerHalf.size()==1, higherHalf.size()==0
            if (higherHalf.isEmpty()) {
                if (num >= lowerHalf.peek())
                    higherHalf.offer(num);
                else {
                    higherHalf.offer(lowerHalf.poll());
                    lowerHalf.offer(num);
                }
                return;
            }
            if (lowerHalf.size() > higherHalf.size()) {
                if (num < lowerHalf.peek()) {
                    higherHalf.offer(lowerHalf.poll());
                    lowerHalf.offer(num);
                } else
                    higherHalf.offer(num);
            } else {// lowerHalf.size() <= higherHalf.size()
                if (num > higherHalf.peek()) {
                    lowerHalf.offer(higherHalf.poll());
                    higherHalf.offer(num);
                } else
                    lowerHalf.offer(num);
            }
        }

        public double findMedian() {
            if (lowerHalf.size() == higherHalf.size())
                return (lowerHalf.peek() + higherHalf.peek()) / 2.0;
            else
                return lowerHalf.peek();
        }
    }

    // 面试题 17.21. 直方图的水量
    // 给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
    // 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。

    // 方法一：（自己写的）动态规划（两次遍历）-时间复杂度：O(n)，空间复杂度：O(n)
    public int trap(int[] height) {
        int n = height.length;
        int[] leftMaxArray = new int[n];
        int leftMax = 0;
        for (int i = 0; i < n; i++) {
            leftMaxArray[i] = leftMax;
            leftMax = Math.max(leftMax, height[i]);
        }

        int[] rightMaxArray = new int[n];
        int rightMax = 0;
        for (int i = n - 1; i >= 0; i--) {
            rightMaxArray[i] = rightMax;
            rightMax = Math.max(rightMax, height[i]);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            int bound = Math.min(leftMaxArray[i], rightMaxArray[i]);
            res += Math.max(bound - height[i], 0);
        }
        return res;
    }
    // 方法二：双指针-时间复杂度：O(n)，空间复杂度：O(1)

    // 方法三：单调栈-时间复杂度：O(n)，空间复杂度：O(n)

    // 面试题 17.22. 单词转换
    // 给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。
    // 编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。

    // 方法一：（自己写的）dfs + 记忆化搜索
    // 常规 dfs 会超时，因为该题只求任意一个可能的转换序列（不要求最短序列），因此可以做简单的记忆化处理，即不还原 visited
    class Solution1722 {
        boolean find = false;
        List<String> ans = new ArrayList<>();
        List<String> res = new ArrayList<>();
        Map<String, List<String>> graph = new HashMap<>();
        Set<String> visited = new HashSet<>();

        public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
            if (!wordList.contains(beginWord))
                wordList.add(beginWord);
            for (String word : wordList) {
                if (!graph.containsKey(word))
                    graph.put(word, new ArrayList<>());
                for (int i = 0; i < word.length(); i++) {
                    String nextWord = getNextWord(word, i);
                    if (!graph.containsKey(nextWord))
                        graph.put(nextWord, new ArrayList<>());
                    graph.get(word).add(nextWord);
                    graph.get(nextWord).add(word);
                }
            }

            if (!graph.containsKey(endWord))
                return res;
            dfs(beginWord, endWord);
            return res;
        }

        private void dfs(String curWord, String endWord) {
            if (find)
                return;
            // dfs结束时，不还原，标记该点为死路，因为遍历图时，可能会由不同路径遍历到同一个节点，再次访问之前去过的节点是做无用功
            visited.add(curWord);
            ans.add(curWord);
            if (curWord.equals(endWord)) {
                find = true;
                res = new ArrayList<>(ans);
                return;
            }
            for (int i = 0; i < curWord.length(); i++) {
                String nextWord = getNextWord(curWord, i);
                for (String nextNextWord : graph.get(nextWord))
                    if (!visited.contains(nextNextWord))
                        dfs(nextNextWord, endWord);
            }
            ans.remove(ans.size() - 1);
        }

        private String getNextWord(String curWord, int index) {
            char[] chars = curWord.toCharArray();
            chars[index] = '*';
            return new String(chars);
        }
    }

    // 面试题 17.23. 最大黑方阵
    // 给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
    // 返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。
    // 若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。
    // 提示：
    // matrix.length == matrix[0].length <= 200

    // 方法一：（自己写的）动态规划-时间复杂度：O(n^3)，空间复杂度：O(n^2)
    public int[] findSquare(int[][] matrix) {
        int n = matrix.length;
        int[][] leftZeros = new int[n][n];
        int[][] upZeros = new int[n][n];

        for (int i = 0; i < n; i++) {
            leftZeros[i][0] = matrix[i][0] == 0 ? 1 : 0;
            for (int j = 1; j < n; j++)
                leftZeros[i][j] = matrix[i][j] == 0 ? leftZeros[i][j - 1] + 1 : 0;
        }

        for (int j = 0; j < n; j++)
            upZeros[0][j] = matrix[0][j] == 0 ? 1 : 0;
        for (int i = 1; i < n; i++)
            for (int j = 0; j < n; j++)
                upZeros[i][j] = matrix[i][j] == 0 ? upZeros[i - 1][j] + 1 : 0;

        int r = 0, c = 0, size = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = Math.min(leftZeros[i][j], upZeros[i][j]); k > size; k--) {
                    if (upZeros[i][j - k + 1] >= k && leftZeros[i - k + 1][j] >= k) {
                        r = i - k + 1;
                        c = j - k + 1;
                        size = k;
                        break;
                    }
                }

        if (size == 0)
            return new int[] {};
        return new int[] { r, c, size };
    }

    // 面试题 17.24. 最大子矩阵
    // 给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
    // 返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。
    // 若有多个满足条件的子矩阵，返回任意一个均可。
    // 注意：本题相对书上原题稍作改动
    // 说明：
    // 1 <= matrix.length, matrix[0].length <= 200

    // 方法一：枚举连续行组合 + 求连续子序列和的最大值-时间复杂度：O(M*N^2)，空间复杂度：O(N)
    // 精髓在于：问题的转化
    public int[] getMaxMatrix(int[][] matrix) {
        /*
         * 降维 + 求连续子序列的和最大值:
         * [[1,2,1,0],
         * [2,1,-1,1],
         * [0,1,2,-1]]
         * 首先遍历出所有的连续行的组合状况[i,j]，其中i<=j
         * 上述例子就是:[0,0],[0,1],[0,2],[1,1],[1,2][2,2]这6种状况
         * 设矩阵有 M 行 N 列
         * 用一个长度为N的数组 sum[N] 存储 [i,j] 连续行内的每一列的和
         * 如:[0,2]行内的sum[0]=3, sum[1]=4, sum[3]=2, sum[4]=0
         * 此时问题就转化为了求sum的连续子序列和的最大值
         * 此时还要维护的是子矩阵的左上角和右下角的坐标
         */
        int M = matrix.length, N = matrix[0].length;
        int[] res = new int[] { -1, -1, 200, 200 };// 结果
        int max = Integer.MIN_VALUE;// 维护子矩阵和的最大值
        long[] sum = null;// sum存储[i,j]连续行内的每一列的和（动态计算）
        int startCol = 0, dp = 0;
        for (int i = 0; i < M; i++) {// 遍历所有连续行的组合,起始行范围为:[0, M-1]
            sum = new long[N];// 每当i(起始行)的位置改变就要重新计算sum
            for (int j = i; j < M; j++) {// 末尾行的范围为:[i, M-1]
                // 重新开始一行就要刷新起始列位置为0，因为dp也在此时进行刷新
                // 换句话说就是接下来计算得到的dp>max时，默认都是从第0列开始计算的
                startCol = 0;
                // dp表示以k结尾的sum数组连续子序列和的最大值,新起一列当然要重新来算
                // 也可以这么理解，子矩阵和就是一维数组sum[k]的和，一行即可
                dp = 0;
                for (int k = 0; k < N; k++) {// k表示遍历matrix[j]的每一个元素matrix[j][k]的索引，范围：[0,N-1]
                    sum[k] += matrix[j][k];// 计算新一行的sum[k]
                    dp += sum[k];// 先计算dp[k]，假设要了sum[k]
                    // 若dp>max表明当前的子矩阵 [i,startCol,j,k] 为对角坐标的子矩阵和>之前的最大值
                    // 说明找到新的最大子矩阵的和，可以更新res了
                    // 归根到底就是在遍历所有以 sum[k] 结尾的情形找到最大值并保存其最大值坐标到res里
                    // 参考"最大连续子数组的和"的状态压缩写法就懂了
                    if (dp > max) {
                        // 更新最大子矩阵和
                        max = dp;
                        // 更新res的对角坐标
                        res[0] = i; // 起始行
                        res[1] = startCol; // 上次另起炉灶的起始列
                        res[2] = j; // 结束行
                        res[3] = k; // 当前刚好加上的第k列
                    }
                    // 若碰到 dp<0 表明当前 sum[startCol,k] 的和将会对后面的起拖累作用
                    // 因此以 k+1 为结尾 sum[k+1] 的不能前面段合并
                    if (dp < 0) {
                        dp = 0;// 后面sum[k+1]结尾的，连续子序列和要另起炉灶
                        startCol = k + 1;// 更新列的起始坐标（不被前面的拖累因此为k+1）
                    }
                }
            }
        }
        return res;
    }

    // 面试题 17.25. 单词矩阵
    // 给定一份单词的清单，设计一个算法，创建由字母组成的面积最大的矩形，
    // 其中每一行组成一个单词(自左向右)，每一列也组成一个单词(自上而下)。
    // 不要求这些单词在清单里连续出现，但要求所有行等长，所有列等高。
    // 如果有多个面积最大的矩形，输出任意一个均可。一个单词可以重复使用。
    // 说明：
    // words.length <= 1000
    // words[i].length <= 100
    // 数据保证单词足够随机

    // 方法一：（自己写的）字典树 + dfs 回溯
    class solution_1725 {
        class Trie {
            Trie[] vals = new Trie[26];
            boolean isEnd;
            boolean hasNext;
        }

        Map<Integer, List<String>> lengthWordMap = new HashMap<>();
        int curRowLength;
        int maxArea = 0;
        List<String> ans = new ArrayList<>();
        List<String> res = new ArrayList<>();

        public String[] maxRectangle(String[] words) {
            // 1. 预处理
            Trie root = new Trie();
            int maxWordLength = 0;
            for (String word : words) {
                // 1.1 根据单词长度分类
                int length = word.length();
                maxWordLength = Math.max(maxWordLength, length);
                if (!lengthWordMap.containsKey(length))
                    lengthWordMap.put(length, new ArrayList<>());
                lengthWordMap.get(length).add(word);

                // 1.2 单词加入字典树
                Trie cur = root;
                for (int i = 0; i < length; i++) {
                    int index = word.charAt(i) - 'a';
                    if (cur.vals[index] == null)
                        cur.vals[index] = new Trie();
                    cur = cur.vals[index];
                    if (i < length - 1)
                        cur.hasNext = true;
                }
                cur.isEnd = true;
            }

            // 初始化roots，记录单词矩阵的对应行的各列字符在字典树中的位置
            Trie[] roots = new Trie[maxWordLength];
            for (int i = 0; i < maxWordLength; i++)
                roots[i] = root;
            // 2. 从最长单词开始dfs
            for (int i = maxWordLength; i >= 1; i--) {
                if (maxArea != 0 && i * i < maxArea)// 后续已经不可能得到更优解了，提前退出循环
                    break;
                curRowLength = i;
                if (lengthWordMap.containsKey(curRowLength))
                    dfs(0, roots);
            }

            return res.toArray(new String[res.size()]);
        }

        private void dfs(int curRow, Trie[] roots) {
            if (curRow == curRowLength)// 单词矩阵的行数超过列数，结束dfs
                return;

            stage1: for (String word : lengthWordMap.get(curRowLength)) {
                for (int i = 0; i < word.length(); i++)
                    // 若选择word，当前行第i列上无对应单词，跳过当前外层循环，当前行上选择下一个单词
                    if (roots[i].vals[word.charAt(i) - 'a'] == null)
                        continue stage1;

                // 选择word后，当前行的各列字符在字典树中的位置
                Trie[] newRoots = new Trie[roots.length];
                for (int i = 0; i < word.length(); i++)
                    newRoots[i] = roots[i].vals[word.charAt(i) - 'a'];

                // 若当前行的每列皆为单词尾，则更新res
                boolean isEnd = true;
                for (int i = 0; i < word.length(); i++) {
                    if (!newRoots[i].isEnd) {
                        isEnd = false;
                        break;
                    }
                }
                ans.add(word);
                if (isEnd && curRowLength * (curRow + 1) > maxArea) {
                    res = new ArrayList<>(ans);
                    maxArea = curRowLength * (curRow + 1);
                }

                // 各列上若无后续单词，则提前剪枝
                boolean hasNext = true;
                for (int i = 0; i < word.length(); i++) {
                    if (!newRoots[i].hasNext) {
                        hasNext = false;
                        break;
                    }
                }
                if (hasNext)
                    dfs(curRow + 1, newRoots);

                ans.remove(ans.size() - 1);// 还原
            }
        }

    }

    // 面试题 17.26. 稀疏相似度
    // 两个(具有不同单词的)文档的交集(intersection)中元素的个数除以并集(union)中元素的个数，就是这两个文档的相似度。
    // 例如，{1, 5, 3} 和 {1, 7, 2, 3} 的相似度是 0.4，其中，交集的元素有 2 个，并集的元素有 5 个。
    // 给定一系列的长篇文档，每个文档元素各不相同，并与一个 ID 相关联。
    // 它们的相似度非常“稀疏”，也就是说任选 2 个文档，相似度都很接近 0。
    // 请设计一个算法返回每对文档的 ID 及其相似度。
    // 只需输出相似度大于 0 的组合。请忽略空文档。为简单起见，可以假定每个文档由一个含有不同整数的数组表示。
    // 输入为一个二维数组 docs，docs[i] 表示 id 为 i 的文档。
    // 返回一个数组，其中每个元素是一个字符串，代表每对相似度大于 0 的文档，
    // 其格式为 {id1},{id2}: {similarity}，
    // 其中 id1 为两个文档中较小的 id，similarity 为相似度，精确到小数点后 4 位。
    // 以任意顺序返回数组均可。
    // 提示：
    // docs.length <= 500
    // docs[i].length <= 500

    // 方法一：（自己写的）哈希表 + 倒排索引-时间复杂度：接近O(n^2)，空间复杂度：O(n^2)
    // 正常写的话复杂度一般都是O(n^3)，会超时
    public List<String> computeSimilarities(int[][] docs) {
        int n = docs.length;
        List<String> res = new ArrayList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();// 倒排索引，num→num出现在的doc的下标
        int[][] intersections = new int[n][n];

        for (int i = 0; i < n; i++) {
            int[] doc = docs[i];
            for (int num : doc) {
                if (!map.containsKey(num))
                    map.put(num, new ArrayList<>());
                List<Integer> list = map.get(num);
                for (int prevAppearanceIndex : list)
                    intersections[prevAppearanceIndex][i]++;
                list.add(i);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int intersection = intersections[i][j];
                if (intersection > 0) {
                    double similarity = (1.0) * intersection / (docs[i].length + docs[j].length - intersection);
                    StringBuilder ans = new StringBuilder();
                    ans.append(i).append(",").append(j).append(": ");
                    ans.append(String.format("%.4f", similarity));
                    res.add(ans.toString());
                }
            }
        }
        return res;
    }
}

public class CodingInterview {

    public static void main(String[] args) {
        
    }
}